bfs广度优先搜索走迷宫

Question

走迷宫(广度优先搜索)

已知一个MxN的迷宫

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

例如迷宫如下：O代表可通行，X代表不可通行

输出最短路径

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

Answer 1

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]);
            }
        }
    }
}

测试地图自己换一下