题解 | #迷宫问题#

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner fzhinput = new Scanner(System.in);
        int hang = fzhinput.nextInt();
        int lie = fzhinput.nextInt();
        int mgsz[][] = new int[hang][lie];
        int h = 0, l = 0;
        for (int i = 0; i < hang; i++) {
            for (int j = 0; j < lie; j++) {
                mgsz[i][j] = fzhinput.nextInt();
            }
        }

        List<int[]> path = findPath(mgsz, hang, lie);

        if (path != null) {
            for (int[] coord : path) {
                System.out.println("(" + coord[0] + "," + coord[1] + ")");
            }
        } else {
            System.out.println("No path found");
        }

        fzhinput.close();
    }
    // 定义方向数组，用于表示四个移动方向：上、下、左、右
    static int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    // BFS 查找最短路径
    public static List<int[]> findPath(int[][] mgsz, int hang, int lie) {
        // 队列用于存储路径中的点，队列中的每个元素是一个三元组 [x, y, 路径]
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0});  // 起点 (0,0)
        
        // 用于记录访问过的点，防止重复访问
        boolean[][] visited = new boolean[hang][lie];
        visited[0][0] = true;
        
        // 用于记录每个点的前驱节点，以便最终还原路径
        int[][][] predecessor = new int[hang][lie][2];
        for (int i = 0; i < hang; i++) {
            for (int j = 0; j < lie; j++) {
                predecessor[i][j] = new int[]{-1, -1};  // 初始化为 -1，表示没有前驱
            }
        }
        
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int x = current[0], y = current[1];
            
            // 如果到达终点，开始构建路径
            if (x == hang - 1 && y == lie - 1) {
                List<int[]> path = new LinkedList<>();
                while (x != -1 && y != -1) {
                    path.add(0, new int[]{x, y});  // 将当前点插入到路径开头
                    int[] pred = predecessor[x][y];  // 获取前驱节点
                    x = pred[0];
                    y = pred[1];
                }
                return path;  // 返回路径
            }
            
            // 尝试四个方向移动
            for (int i=0;i<4;i++) {
                int newX = x + directions[i][0];
                int newY = y + directions[i][1];
                
                // 检查是否在边界内，是否可以走（值为 0），且没有访问过
                if (newX >= 0 && newX < hang && newY >= 0 && newY < lie 
                    && mgsz[newX][newY] == 0 && !visited[newX][newY]) {
                    
                    visited[newX][newY] = true;  // 标记为已访问
                    queue.offer(new int[]{newX, newY});  // 将该点加入队列
                    predecessor[newX][newY] = new int[]{x, y};  // 记录前驱节点
                }
            }
        }
        
        return null;  // 如果找不到路径，返回 null
    }
    
}