题解 | #迷宫问题#

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static List<int[]> path = new ArrayList<>();  // 当前路径
    static List<int[]> minPath = new ArrayList<>();  // 最短路径
    static int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    static int[][] grid;
    static int m, n;
    static boolean[][] vis;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        m = Integer.parseInt(str.split(" ")[0]);
        n = Integer.parseInt(str.split(" ")[1]);
        grid = new int[m][n];
        vis = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            String[] strs = sc.nextLine().split(" ");
            for (int j = 0; j < n; j++) {
                grid[i][j] = Integer.parseInt(strs[j]);
            }
        }
        // System.out.println(Arrays.deepToString(grid));
        // 先标记和加入path再dfs
        vis[0][0] = true;
        path.add(new int[] {0, 0});
        dfs(0, 0);
        for (int[] p : minPath) {
            System.out.println("(" + p[0] + "," + p[1] + ")");
        }
    }

    private static void dfs(int i, int j) {
        if (i == m - 1 && j == n - 1) {
            // 当前为首条合法路径 || 当前路径比之前最短路径更短 -> 更新最短路径
            if (minPath.size() == 0 || path.size() < minPath.size()) {
                minPath = new ArrayList<>(path);
            }
            // 撤回再结束
            path.remove(path.size() - 1);
            vis[i][j] = false;
            return;
        }
        for (int[] d : dirs) {
            int nextI = i + d[0], nextJ = j + d[1];
            // 范围内&&没走过&&能走
            if (nextI >= 0 && nextI < m && nextJ >= 0 && nextJ < n && !vis[nextI][nextJ] &&
                    grid[nextI][nextJ] == 0) {
                // 先标记
                vis[nextI][nextJ] = true;
                path.add(new int[] {nextI, nextJ});
                // 进行dfs
                dfs(nextI, nextJ);
                // 撤回
                vis[nextI][nextJ] = false;
                path.remove(path.size() - 1);
            }
        }
    }
}