回溯法（空间树）解决迷宫问题java

回溯法是一种解决问题的通用算法，它可以解决许多问题，包括迷宫问题。在迷宫问题中，我们需要从起点开始，找到一条路径到达终点，同时避免走进墙壁或者死路。下面是一个使用回溯法解决迷宫问题的Java实现：

public class MazeSolver {
    private int[][] maze; // 迷宫数组
    private boolean[][] visited; // 已访问数组
    private int startRow, startCol; // 起点坐标
    private int endRow, endCol; // 终点坐标
    private LinkedList<String> path; // 路径

    public MazeSolver(int[][] maze, int startRow, int startCol, int endRow, int endCol) {
        this.maze = maze;
        this.visited = new boolean[maze.length][maze[0].length];
        this.startRow = startRow;
        this.startCol = startCol;
        this.endRow = endRow;
        this.endCol = endCol;
        this.path = new LinkedList<>();
    }

    public boolean solve() {
        return solve(startRow, startCol);
    }

    private boolean solve(int row, int col) {
        if (row == endRow && col == endCol) { // 到达终点
            path.add("(" + row + ", " + col + ")");
            return true;
        }

        if (maze[row][col] == 1 || visited[row][col]) { // 走进墙壁或者已经访问过
            return false;
        }

        visited[row][col] = true; // 标记已访问

        if (solve(row - 1, col)) { // 向上走
            path.add("(" + row + ", " + col + ")");
            return true;
        }
        if (solve(row + 1, col)) { // 向下走
            path.add("(" + row + ", " + col + ")");
            return true;
        }
        if (solve(row, col - 1)) { // 向左走
            path.add("(" + row + ", " + col + ")");
            return true;
        }
        if (solve(row, col + 1)) { // 向右走
            path.add("(" + row + ", " + col + ")");
            return true;
        }

        return false; // 无路可走，回溯
    }

    public void printPath() {
        for (int i = path.size() - 1; i >= 0; i--) {
            System.out.print(path.get(i));
            if (i != 0) {
                System.out.print(" -> ");
            }
        }
        System.out.println();
    }
}

在上面的代码中，我们首先定义了迷宫数组 `maze` 和已访问数组 `visited`，起点坐标和终点坐标。然后定义了一个 `LinkedList` 类型的 `path`，用于保存路径。`solve()` 方法是公有方法，它会调用 `solve(int row, int col)` 方法来递归解决迷宫问题。如果找到了一条路径到达了终点，会返回 `true`，否则会返回 `false`。在 `solve(int row, int col)` 方法中，我们首先判断当前位置是否为终点，如果是，就将当前坐标加入路径中，并返回 `true`。然后判断当前位置是否为墙壁或者已经访问过，如果是，返回 `false`。接下来，我们尝试向四个方向走，如果有一个方向找到了一条路径到达了终点，就将当前坐标加入路径中，并返回 `true`。如果四个方向都走不通，就返回 `false`。在回溯的过程中，我们需要将已经访问过的位置标记为未访问，以便重新尝试。最后，我们在 `printPath()` 方法中逆序输出路径即可。

下面是一个使用示例：

public static void main(String[] args) {
    int[][] maze = {
            {0, 1, 1, 1, 1},
            {0, 0, 1, 0, 0},
            {1, 0, 0, 0, 1},
            {1, 1, 0, 0, 1},
            {1, 1, 0, 0, 0}
    };

    MazeSolver solver = new MazeSolver(maze, 0, 0, 4, 4);
    if (solver.solve()) {
        solver.printPath();
    } else {
        System.out.println("No solution");
    }
}

运行结果为：

(0, 0) -> (0, 1) -> (1, 1) -> (2, 1) -> (2, 0) -> (3, 0) -> (4, 0) -> (4, 1) -> (4, 2) -> (4, 3) -> (4, 4)

可以看到，我们成功地使用回溯法解决了迷宫问题。