题解 | #迷宫问题#

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextInt()) {
            int row = scanner.nextInt();
            int col = scanner.nextInt();
            int[][] arr = new int[row][col]; // 开辟a*b二维数组
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    int num = scanner.nextInt();
                    arr[i][j] = num;
                }
            }
            ArrayList<ArrayList<Position>> results = new ArrayList<ArrayList<Position>>(); // 存储真正的结果集。
            ArrayList<Position> path = new ArrayList<>(); // 存储走过的路径
            backTrace(path,results,arr,0,0);
            for (ArrayList<Position> list:results) {
                for (Position vo:list) {
                    System.out.println("(" + vo.i +"," + vo.j + ")");
                }
            }
        }
    }

    private static void backTrace(ArrayList<Position> path, ArrayList<ArrayList<Position>> results, int[][] arr, int i, int j) {
        if (i >= arr.length ||i < 0 || j < 0 || j >= arr[i].length) {
            return;
        }
        if (arr[i][j] != 0) { // 可能是墙壁1，可能是走过的路3.
            return;
        }

        if (arr[i][j] == 0) { // 该点为0，说明暂时能走
            if (i == arr.length-1 && j == arr[i].length-1) {// 到达右下角
                path.add(new Position(i,j)); // 添加进入路径
                results.add(new ArrayList<>(path)); // 此刻才是真正我们所需的路径结果
            }
            path.add(new Position(i,j));//添加进路径
            arr[i][j] = 3;// 走过标记为3，防止递归在原地打转。这样回到走过的点时就会退出。
        }

        backTrace(path,results,arr,i-1,j); //上
        backTrace(path,results,arr,i+1,j);//下
        backTrace(path,results,arr,i,j-1);//左
        backTrace(path,results,arr,i,j+1);//右
        path.remove(path.size()-1); // 走完四个分支，退出时，说明该点走不通，要从路径集合中撤销掉

    }

    public static class Position {
        int i;
        int j;
        public Position(int i,int j) {
            this.i = i;
            this.j = j;
        }
    }


}