题解 | #迷宫问题#

import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;

public class Main {
    static Stack<String> paths = new Stack<>();

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int row = in.nextInt();
        int col = in.nextInt();
        int[][] maze = new int[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                maze[i][j] = in.nextInt();
            }
        }
        in.close();
        findWay(maze,0, 0, row - 1, col - 1);
        // 将一开始起点(0, 0)加入stack中
        paths.push("(0,0)");
        while (!paths.isEmpty()) {
            if (paths.size() > 1) {
                System.out.println(paths.pop());
            } else {
                // 最后一次回溯带了一个多余的路程进去，我们将其去除
                paths.pop();
            }
        }
    }

    /**
     * 使用递归回溯来找路
     * @param map 表示地图
     * @param i 起点从哪一行开始
     * @param j 起点从哪一列开始
     * @param m 表示终点的行位置
     * @param n 表示终点的列位置
     * @return 如果找到通路则返回true
     * 约定：0 表示没有走过的空位，1 表示墙壁，2 表示通路可以走，3 表示该点已经走过但是走不通
     * 在走迷宫的时候，需要确定一个策略（方法），下 -> 右 -> 上 -> 左，如果该点走不通再回溯
     */
    public static boolean findWay(int[][] map, int i, int j, int m, int n) {
        if (map[m][n] == 2) { // 通路已经找到，结束
            return true;
        } else {
            if (map[i][j] == 0) { // 如果当前这个点还没走过，仅仅0点才可以去走，因为其他路都是走过或者墙，不可以继续往下走
                // 按照策略走 下 -> 右 -> 上 -> 左
                map[i][j] = 2; // 假定该点是可以走通的，并在此基础上判断该点能否再往其他方向走
                if (i + 1 <= m && findWay(map, i + 1, j, m, n)) { // 判断能否向下走
                    paths.push("(" + (i + 1) + "," + j +")");
                    return true;
                } else if (j + 1 <= n && findWay(map, i, j + 1, m, n)) { // 判断能否向右走
                    paths.push("(" + i + "," + (j + 1) +")");
                    return true;
                } else if (i - 1 >= 0 && findWay(map, i - 1, j, m, n)) { // 判断能否向上走
                    paths.push("(" + (i - 1) + "," + j +")");
                    return true;
                } else if (j - 1 >= 0 && findWay(map, i, j - 1, m, n)) { // 判断能否向左走
                    paths.push("(" + i + "," + (j - 1) +")");
                    return true;
                } else {
                    // 说明该点是走不通的，是死路
                    map[i][j] = 3;
                    return false;
                }
            } else {
                // 如果 map[i][j] != 0，有可能是 1，2 的情况，说明这个点在之前已经知道不能走下去了
                return false;
            }
        }
    }

    public static void showMap(int[][] map) {
        System.out.println("地图的情况如下图所示：");
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                System.out.print(map[i][j] + "  ");
            }
            System.out.println();
        }
    }
}