DeiaaaW 2023-04-06 11:38 采纳率: 100%
浏览 11
已结题

bfs广度优先搜索走迷宫

走迷宫(广度优先搜索)

已知一个MxN的迷宫

求从(0,0)到(M-1,N-1)的最短路径

例如迷宫如下:O代表可通行,X代表不可通行

img

输出最短路径

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<int[]> queue = new LinkedList<>();
            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<>();
                            path.add(new int[]{nx, ny});
                            int cur_x = x, cur_y = y;
                            while (cur_x != start_x || cur_y != start_y) {
                                path.add(new int[]{cur_x, cur_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;
                                    }
                                }
                            }
                            path.add(new int[]{start_x, start_y});
                            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]);
                }
            }
        }
    }
    

    测试地图自己换一下

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
  • CSDN-Ada助手 CSDN-AI 官方账号 2023-04-07 22:17
    关注
    不知道你这个问题是否已经解决, 如果还没有解决的话:

    如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^
    评论
查看更多回答(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使用问题