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 vue+element 生成table
• ¥15 实验 4 FIFO 算法和 LRU 算法-C 程序实现
• ¥30 电脑画面同步投屏，通过同wifi的方式投屏方法，接收投屏端不需要安装第三方软件，
• ¥15 有偿拼接大疆精灵4RGB影像
• ¥15 MATLAB特殊符号
• ¥15 Arduino实现音频混响
• ¥15 cuda.jit加速报错
• ¥15 Octave 安装工具箱出错 Only Win32 target is supported!
• ¥15 docker save的不能在另一台设备运行
• ¥15 Unity Animation Rigging使用问题