java回溯算法解决迷宫问题

回溯算法是解决迷宫问题的常见方法，下面通过 Java 代码来实现：

public class Maze {
    private static final int N = 8;
    private static final int[][] maze = {
            {0, 0, 0, 0, 0, 0, 0, 1},
            {0, 1, 1, 0, 1, 1, 0, 1},
            {0, 0, 0, 1, 0, 0, 0, 1},
            {0, 0, 0, 0, 1, 1, 0, 0},
            {1, 1, 0, 0, 0, 0, 1, 1},
            {1, 1, 0, 0, 0, 0, 1, 1},
            {0, 0, 0, 1, 1, 0, 0, 1},
            {0, 0, 0, 0, 0, 0, 0, 1}
    };

    private static final int PATHWAY_COLOUR = 0; // 通道颜色
    private static final int WALL_COLOUR = 1; // 墙颜色
    private static final int BLOCKED_COLOUR = 2; // 被阻挡的颜色
    private static final int PATH_COLOUR = 3; // 路径颜色

    public static boolean findMazePath(int x, int y) {
        if (x < 0 || y < 0 || x >= N || y >= N) { // 越界
            return false;
        } else if (maze[x][y] != PATHWAY_COLOUR) { // 不是通道
            return false;
        } else if (x == N - 1 && y == N - 1) { // 到达终点
            maze[x][y] = PATH_COLOUR; // 标记为路径颜色
            return true;
        } else {
            maze[x][y] = PATH_COLOUR; // 标记为路径颜色
            if (findMazePath(x - 1, y) || findMazePath(x, y + 1) || findMazePath(x + 1, y) || findMazePath(x, y - 1)) {
                return true;
            }
            maze[x][y] = BLOCKED_COLOUR; // 标记为被阻挡的颜色
            return false;
        }
    }

    public static void printMaze() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print(maze[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        findMazePath(0, 0);
        printMaze();
    }
}

上述代码中，通过 `findMazePath` 方法实现了回溯算法的递归过程，判断当前位置是否越界或者是不通的墙，如果到达终点就标记为路径颜色，否则尝试四个方向进行递归查找，如果四个方向都无法到达终点，就标记为被阻挡的颜色。最终通过 `printMaze` 方法输出迷宫的状态。