java回溯算法解决迷宫问题

回溯算法可以很好地解决迷宫问题。下面是一个Java实现的示例代码：

import java.util.*;

public class Maze {
    private int[][] maze; // 迷宫矩阵
    private int rows; // 行数
    private int cols; // 列数
    private int startX; // 起点横坐标
    private int startY; // 起点纵坐标
    private int endX; // 终点横坐标
    private int endY; // 终点纵坐标
    private boolean[][] visited; // 记录走过的位置

    public Maze(int[][] maze, int startX, int startY, int endX, int endY) {
        this.maze = maze;
        this.rows = maze.length;
        this.cols = maze[0].length;
        this.startX = startX;
        this.startY = startY;
        this.endX = endX;
        this.endY = endY;
        this.visited = new boolean[rows][cols];
    }

    public void solve() {
        List<int[]> path = new ArrayList<>(); // 记录路径
        boolean found = backtrack(startX, startY, path);
        if (found) {
            System.out.println("Solution found:");
            for (int[] p : path) {
                System.out.print(Arrays.toString(p) + " ");
            }
        } else {
            System.out.println("No solution found.");
        }
    }

    private boolean backtrack(int x, int y, List<int[]> path) {
        if (x == endX && y == endY) {
            path.add(new int[]{x, y});
            return true;
        }
        if (maze[x][y] == 1 || visited[x][y]) {
            return false;
        }
        path.add(new int[]{x, y});
        visited[x][y] = true;
        if (x > 0 && backtrack(x - 1, y, path)) {
            return true;
        }
        if (x < rows - 1 && backtrack(x + 1, y, path)) {
            return true;
        }
        if (y > 0 && backtrack(x, y - 1, path)) {
            return true;
        }
        if (y < cols - 1 && backtrack(x, y + 1, path)) {
            return true;
        }
        path.remove(path.size() - 1); // 回溯
        return false;
    }

    public static void main(String[] args) {
        int[][] maze = {
            {0, 1, 0, 0},
            {0, 0, 0, 1},
            {1, 0, 0, 0},
            {1, 1, 0, 0},
            {1, 1, 1, 0}
        };
        Maze m = new Maze(maze, 0, 0, 4, 3);
        m.solve();
    }
}

在这个示例代码中，我们使用了递归的回溯算法来解决迷宫问题。当我们到达终点时，将路径添加到路径列表中并返回true。否则，我们按照上、下、左、右的顺序依次探索可行的路径。如果找到了一条可行路径，则返回true。如果所有的路径都无法到达终点，则回溯到上一步并返回false。最后，我们将找到的路径打印出来。