题解 | 迷宫问题

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int h = scanner.nextInt();
        int w = scanner.nextInt();
        int[][] maze = new int[h][w];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                maze[i][j] = scanner.nextInt();
            }
        }

        int[][] dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; // 下、右、上、左的顺序

        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] {0, 0});

        boolean[][] visited = new boolean[h][w];
        visited[0][0] = true;

        int[][] prevX = new int[h][w];
        int[][] prevY = new int[h][w];
        for (int i = 0; i < h; i++) {
            Arrays.fill(prevX[i], -1);
            Arrays.fill(prevY[i], -1);
        }

        int[] end = {h - 1, w - 1};
        boolean found = false;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int x = current[0];
            int y = current[1];

            if (x == end[0] && y == end[1]) {
                found = true;
                break;
            }

            for (int[] dir : dirs) {
                int nx = x + dir[0];
                int ny = y + dir[1];

                if (nx >= 0 && nx < h && ny >= 0 && ny < w && maze[nx][ny] == 0 &&
                        !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    prevX[nx][ny] = x;
                    prevY[nx][ny] = y;
                    queue.add(new int[] {nx, ny});
                }
            }
        }

        List<int[]> path = new ArrayList<>();
        int[] current = end;
        while (current[0] != 0 || current[1] != 0) {
            path.add(current);
            int px = prevX[current[0]][current[1]];
            int py = prevY[current[0]][current[1]];
            current = new int[] {px, py};
        }
        path.add(new int[] {0, 0});

        Collections.reverse(path);

        for (int[] p : path) {
            System.out.println("(" + p[0] + "," + p[1] + ")");
        }
    }
}

https://www.nowcoder.com/discuss/727521113110073344

思路

1.输入处理：读取迷宫的行数和列数，以及迷宫的布局。

2.BFS 初始化：使用队列进行广度优先搜索，初始化起点，并标记为已访问。

3.前驱数组：记录每个节点的前驱节点，以便回溯路径。

4.遍历方向：按照下、右、上、左的顺序处理每个节点的相邻节点，确保路径搜索的顺序。

5.路径回溯：从终点出发，根据前驱节点数组回溯到起点，并将路径逆序输出。