DeiaaaW 2023-04-06 11:38 采纳率: 100%

bfs广度优先搜索走迷宫

7,7

6,7

6,6

5,6

5,5

5,4

4,4

3,4

2,4

1,4

1,3

1,2

1,1

1,0

0,0

• 写回答

2条回答默认 最新

• Dummer25 2023-04-06 16:03
关注
``````import java.util.*;

public class MazeBFS {
// 迷宫地图
private char[][] maze;
// 迷宫大小
private int M, N;
// 上下左右四个方向
private int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
// 记录已访问的位置
private boolean[][] visited;

public MazeBFS(char[][] maze) {
this.maze = maze;
this.M = maze.length;
this.N = maze[0].length;
this.visited = new boolean[M][N];
}

// 广度优先搜索
public List<int[]> bfs(int start_x, int start_y, int end_x, int end_y) {
queue.offer(new int[]{start_x, start_y});
visited[start_x][start_y] = true;
while (!queue.isEmpty()) {
int[] pos = queue.poll();
int x = pos[0], y = pos[1];
for (int[] dir : directions) {
int nx = x + dir[0], ny = y + dir[1];
if (nx >= 0 && nx < M && ny >= 0 && ny < N && maze[nx][ny] == 'O' && !visited[nx][ny]) {
visited[nx][ny] = true;
if (nx == end_x && ny == end_y) {
List<int[]> path = new ArrayList<>();
int cur_x = x, cur_y = y;
while (cur_x != start_x || cur_y != start_y) {
for (int[] dir2 : directions) {
int prev_x = cur_x - dir2[0], prev_y = cur_y - dir2[1];
if (prev_x >= 0 && prev_x < M && prev_y >= 0 && prev_y < N && visited[prev_x][prev_y]) {
cur_x = prev_x;
cur_y = prev_y;
break;
}
}
}
Collections.reverse(path);
return path;
}
queue.offer(new int[]{nx, ny});
}
}
}
return null;
}

public static void main(String[] args) {
// 迷宫地图
char[][] maze = {
{'O', 'O', 'O', 'O', 'O', 'X', 'O', 'O'},
{'X', 'O', 'X', 'X', 'O', 'X', 'O', 'X'},
{'O', 'O', 'O', 'O', 'O', 'O', 'O', 'O'},
{'O', 'X', 'X', 'O', 'X', 'X', 'O', 'X'},
{'O', 'O', 'O', 'O', 'X', 'O', 'O', 'O'},
{'X', 'O', 'X', 'O', 'O', 'O', 'X', 'O'},
{'X', 'X', 'O', 'O', 'X', 'O', 'O', 'O'},
};

MazeBFS solution = new MazeBFS(maze);
List<int[]> shortestPath= solution.bfs(0, 0, maze.length - 1, maze[0].length - 1);
if (shortestPath == null) {
System.out.println("无法到达终点！");
} else {
System.out.println("最短路径为：");
for (int[] pos : shortestPath) {
System.out.println(pos[0] + " " + pos[1]);
}
}
}
}
``````

测试地图自己换一下

本回答被题主选为最佳回答 , 对您是否有帮助呢?
评论

• 系统已结题 4月28日
• 已采纳回答 4月20日
• 创建了问题 4月6日

悬赏问题

• ¥15 mmo能不能做客户端怪物
• ¥15 osm下载到arcgis出错
• ¥15 Dell g15 每次打开eiq portal后3分钟内自动退出
• ¥200 使用python编写程序，采用socket方式获取网页实时刷新的数据，能定时print（）出来就行。
• ¥15 matlab如何根据图片中的公式绘制e和v的曲线图
• ¥15 我想用Python（Django）+Vue搭建一个用户登录界面，但是在运行npm run serve时报错了如何解决？
• ¥15 QQ邮箱过期怎么恢复？
• ¥15 登录他人的vue项目显示服务器错误
• ¥15 (标签-android|关键词-app)
• ¥15 comsol仿真压阻传感器