题解 | 迷宫问题

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {

    public static int[][] maze;
    public static Stack<int[]> tempPath = new Stack<>();
    public static Stack<int[]> bestPath = new Stack<>();

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int m = in.nextInt();
            maze = new int[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    maze[i][j] = in.nextInt();
                }
            }
            tempPath.clear();
            bestPath.clear();

            mazeTrack(0, 0);
            bestPath.forEach(o-> System.out.printf("(%d,%d)%n",o[0], o[1]));
        }
    }

    private static void mazeTrack(int i, int j) {
        maze[i][j] = 1;
        tempPath.push(new int[] {i, j});
        if (i == maze.length - 1 && j == maze[0].length - 1) {//到达终点
            if (bestPath.empty() ||
                    bestPath.size() > tempPath.size()) { // 判斷是否最短路径
                bestPath.addAll(tempPath);
            }
        }

        if (i - 1 >= 0 && maze[i - 1][j] == 0) {// 向上走，没有墙
            mazeTrack(i - 1, j);
        }
        if (i + 1 <= maze.length - 1 && maze[i + 1][j] == 0) {// 向下走，没有墙
            mazeTrack(i + 1, j);
        }
        if (j - 1 >= 0 && maze[i][j - 1] == 0) {// 向左走，没有墙
            mazeTrack(i, j - 1);
        }
        if (j + 1 <= maze[0].length - 1 &&
                maze[i][j + 1] == 0) {// 向右走，没有墙
            mazeTrack(i, j + 1);
        }

        maze[i][j] = 0;
        tempPath.pop();
    }
}