回溯算法解决迷宫问题java

回溯算法可以很好地解决迷宫问题，以下是Java代码实现：

public class Maze {

    private int[][] maze; // 迷宫矩阵
    private int[] start; // 起点坐标
    private int[] end; // 终点坐标
    private int[][] path; // 已经走过的路径

    public Maze(int[][] maze, int[] start, int[] end) {
        this.maze = maze;
        this.start = start;
        this.end = end;
        this.path = new int[maze.length][maze[0].length];
    }

    public void solve() {
        if (findPath(start[0], start[1])) {
            printPath();
        } else {
            System.out.println("No solution!");
        }
    }

    private boolean findPath(int x, int y) {
        if (x < 0 || x >= maze.length || y < 0 || y >= maze[0].length || maze[x][y] == 1 || path[x][y] == 1) {
            return false;
        }

        path[x][y] = 1;

        if (x == end[0] && y == end[1]) {
            return true;
        }

        if (findPath(x + 1, y) || findPath(x, y + 1) || findPath(x - 1, y) || findPath(x, y - 1)) {
            return true;
        }

        path[x][y] = 0;

        return false;
    }

    private void printPath() {
        for (int i = 0; i < maze.length; i++) {
            for (int j = 0; j < maze[0].length; j++) {
                if (path[i][j] == 1) {
                    System.out.print("X ");
                } else {
                    System.out.print(maze[i][j] + " ");
                }
            }
            System.out.println();
        }
    }
}

使用方法：

int[][] maze = {
        {0, 1, 0, 0, 0},
        {0, 1, 0, 1, 0},
        {0, 0, 0, 0, 0},
        {0, 1, 1, 1, 0},
        {0, 0, 0, 1, 0}
};
int[] start = {0, 0};
int[] end = {4, 4};
Maze m = new Maze(maze, start, end);
m.solve();

输出结果：

0 X 0 0 0 
0 X 0 X 0 
0 X X X 0 
0 0 0 X 0 
0 0 0 X 0