题解 | 迷宫问题

import java.util.Scanner;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

/**
 * 迷宫问题
 */
public class Main {

    private static final int[] dx = {-1, 1, 0, 0};
    private static final int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int h = sc.nextInt();
            int w = sc.nextInt();

            int[][] grid = new int[h][w];
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    grid[i][j] = sc.nextInt();
                }
            }

            Queue<int[]> queue = new ArrayDeque<>();
            int[] root = {0, 0};
            queue.offer(root);

            // 记录前一个路径
            int[][][] parent = new int[h][w][2];

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

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

                // break条件，x,y是终点
                if (x == h - 1 && y == w - 1) break;

                // 从四个方向进行遍历
                for (int i = 0; i < 4; i++) {
                    int nx = x + dx[i];
                    int ny = y + dy[i];


                    // 坐标有效，且可以通行
                    if (nx >= 0 && nx < h && ny >= 0 && ny < w && grid[nx][ny] == 0 &&
                            !visited[nx][ny]) {
                        parent[nx][ny][0] = x;
                        parent[nx][ny][1] = y;
                        queue.offer(new int[] {nx, ny});
                        visited[nx][ny] = true;
                    }
                }
            }

            // 回溯路径
            List<String> path = new ArrayList<>();
            int cx = h - 1, cy = w - 1;
            while (cx != 0 || cy != 0) {
                // 添加目的地坐标
                path.add("(" + cx + "," + cy + ")");
                // 获取终点的前驱坐标
                int px = parent[cx][cy][0];
                int py = parent[cx][cy][1];
                // 继续向前查找，找到前一个坐标
                cx = px;
                cy = py;
            }
            // 添加终点
            path.add("(0,0)");
            Collections.reverse(path);

            // 格式化输出
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < path.size(); i++) {
                sb.append(path.get(i));
                if (i < path.size() - 1) sb.append("\n");
            }
            System.out.println(sb);
        }
        sc.close();
    }
}