public class MazeTest{

    //  迷宫，9行8列
    private static int ROW = 9;
    private static int COLUMN = 8;
    private static int[][] maze = {
        {1, 1, 0, 1, 1, 1, 0, 1},
        {1, 1, 0, 1, 1, 1, 0, 1},
        {1, 1, 0, 1, 0, 0, 1, 0},
        {1, 0, 0, 0, 1, 1, 0, 1},
        {1, 1, 1, 0, 1, 1, 1, 1},
        {1, 0, 1, 1, 1, 0, 1, 0},
        {1, 0, 0, 0, 0, 1, 1, 0},
        {0, 0, 1, 1, 1, 0, 1, 0},
        {0, 0, 1, 1, 1, 1, 1, 1}
    };


    public static void main(String[] args) {
        
        // 从左上角开始走迷宫
        walk(0, 0);
    }

    public static void walk(int i , int j){

        // 如果到达右下角，说明该路线可以走通
        if (i >= ROW-1 && j >= COLUMN-1) {
            //  打印当前迷宫痕迹
            System.out.println("找到一种解法如下：====");
            for (int r = 0; r < ROW; r++) {
                for (int c = 0; c < COLUMN; c++) {
                    System.out.print(maze[r][c]);
                }
                System.out.println();
            }
            return;
        } // ===打印迷宫结束

        // 向右走，先查查是否可以站在这个i, j+1 这个点上
        if (canStand(i, j+1)) {
            // 可以站在这个点上，站上去（标记已走过）
            maze[i][j] = 6;
            walk(i, j+1); // 往右走，进入下一个历史宇宙
            // 在最右边历史宇宙撞墙了，这个宇宙上面把这个点改为6了，需要改回来，否则篡改历史，会引发未知的蝴蝶效应
            maze[i][j] = 1;
        }

        // 在最右历史宇宙中走不下去，向下走
        if (canStand(i+1, j)) {
            maze[i][j] = 6;
            walk(i+1, j);
            maze[i][j] = 1;
        }

        // 向左走
        if (canStand(i, j-1)) {
            maze[i][j] = 6;
            walk(i, j-1);
            maze[i][j] = 1;
        }

        // 向上走
        if (canStand(i-1, j)) {
            maze[i][j] = 6;
            walk(i - 1, j);
            maze[i][j] = 1;
        }

    }

    private static boolean canStand(int i, int j) {
        //System.out.print("[" + i + "," + j + "]=>");
        //  走到边界了
        if (i >= ROW || j >= COLUMN || i < 0 || j < 0) {
            return false;
        }

        // 遇到障碍了
        if (maze[i][j] == 0) {
            return false;
        }

        // 走过了
        if (maze[i][j] == 6) {
            return false;
        }
        return true;
    }
}