题解 | #迷宫问题#

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {

    // 存储所有的潜在路径,本题目前只有1个路径
    static ArrayList<LinkedList<int[]>> result = new ArrayList<>();
    static LinkedList<int[]> paths = new LinkedList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int rowSize = sc.nextInt();
        int colSize = sc.nextInt();
        int[][] map = new int[rowSize][colSize];
        for (int i = 0; i < rowSize; i++) {
            for (int j = 0; j < colSize; j++) {
                map[i][j] = sc.nextInt();
            }
        }
        helper(map, 0, 0);
        // 默认只有一个解法，result取第一个即可
        for (int[] path : result.get(0)) {
            System.out.println("(" + path[0] + "," + path[1] + ")");
        }
    }

    private static void helper(int[][] map, int x, int y) {
        int rowSize = map.length;
        int colSize = map[0].length;

        // 越界 or 碰壁 return
        if (x < 0 || x >= rowSize || y < 0 || y >= colSize || map[x][y] == 1) {
            return;
        }

        if (x == rowSize - 1 && y == colSize - 1) {
            // 注意加上末尾节点
            paths.add(new int[]{x, y});
            // 注意要生成一个新的path list，否则回溯会把这个清空
            result.add(new LinkedList<>(paths));
        } else {
            // 污染思想，上下左右
            map[x][y] = 1;
            paths.add(new int[]{x, y});
            helper(map, x + 1, y);
            helper(map, x - 1, y);
            helper(map, x, y + 1);
            helper(map, x, y - 1);
            // 回溯
            map[x][y] = 0;
            paths.removeLast();
        }
    }
}