题解 | 迷宫问题

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static int[] actions = new int[] {1, 0, -1, 0, 1};
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int h = in.nextInt();
        int w = in.nextInt();
        int[][] matrix = new int[h][w];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                matrix[i][j] = in.nextInt();
            }
        }
        ArrayList<int[]> res = new ArrayList<>();
        ArrayList<int[]> curPath = new ArrayList<>();
        curPath.add(new int[] {0, 0});
        boolean[][] isVisited = new boolean[h][w];
        dfs(matrix, isVisited, 0, 0, curPath, res);
        for (int[] node : res) {
            System.out.println(String.format("(%d,%d)", node[0], node[1]));
        }
    }

    private static void dfs(int[][] matrix, boolean[][] isVisited, int i, int j,
                            ArrayList<int[]> curPath,
                            ArrayList<int[]> res) {
        if (i == matrix.length - 1 && j == matrix[0].length - 1) {
            res.addAll(curPath);
            return;
        } else {
            isVisited[i][j] = true;
            //从ij向四个方向探索
            for (int a = 0; a < 4; a++) {
                int nextI = i + actions[a];
                int nextJ = j + actions[a + 1];
                if (nextI >= 0 && nextJ >= 0 && nextI < matrix.length &&
                        nextJ < matrix[0].length) {
                    if (matrix[nextI][nextJ] == 0 && !isVisited[nextI][nextJ]) {
                        curPath.add(new int[] {nextI, nextJ});
                        dfs(matrix, isVisited, nextI, nextJ, curPath, res);
                        curPath.remove(curPath.size() - 1);
                    }
                }
            }
        }
    }
}