Java递归寻路实现，你真的理解了吗

什么是递归寻路

递归寻路是指在迷宫等场景下，从起点开始，不断地试探路径并标记已经探测的路径，直到找到终点或是所有可达路径都已探测过的过程。

实现思路

在 Java 中，可以通过递归函数来实现寻路的过程。具体来说，我们可以编写下面这个函数 findPath：

public static boolean findPath(int x, int y, int[][] maze, int[][] path) {
    if (x < 0 || x >= maze.length || y < 0 || y >= maze[0].length || maze[x][y] == 1 || path[x][y] == 1) {
        // 如果越界了，或是碰到了障碍，或是已经在当前路径上，返回 false
        return false;
    }
    if (x == maze.length - 1 && y == maze[0].length - 1) {
        // 如果已经到达终点，返回 true
        return true;
    }
    path[x][y] = 1;  // 标记当前位置已经探测过
    // 在当前位置的上、下、左、右四个方向递归查找路径
    if (findPath(x, y - 1, maze, path) || findPath(x - 1, y, maze, path) || 
        findPath(x, y + 1, maze, path) || findPath(x + 1, y, maze, path)) {
        return true;
    }
    path[x][y] = 0;  // 如果当前位置没有通行，将其标记为未探测过，以便后续查找可以重新探测
    return false;
}

在该函数中，我们传入了起点的坐标 (x, y)、迷宫数组 maze 和路径数组 path。迷宫数组中的 0 表示通行，1 表示障碍，路径数组中的 0 表示未探测，1 表示已探测。函数返回值为是否找到终点的布尔值。

在函数中，我们首先进行参数的检查，如果越界或碰到障碍或已在路径上，则返回 false。然后，检查是否已到达终点，如果是，返回 true。接着，在当前位置的上、下、左、右四个方向递归调用 findPath 函数，如果有一个方向能够找到终点，就返回 true。最后，将当前位置标记为未探测过，并返回 false。

示例1

假设有一个如下所示的迷宫：

01110
00000
11111
00110
01000

其中 0 表示通行，1 表示障碍。起点为 (0, 0)，终点为 (4, 3)。我们可以通过下面这段代码来寻路：

int[][] maze = {{0, 1, 1, 1, 0},
                {0, 0, 0, 0, 0},
                {1, 1, 1, 1, 1},
                {0, 0, 1, 1, 0},
                {0, 1, 0, 0, 0}};
int[][] path = new int[maze.length][maze[0].length];
if (findPath(0, 0, maze, path)) {
    System.out.println("找到了一条路径：");
    for (int i = 0; i < path.length; i++) {
        for (int j = 0; j < path[0].length; j++) {
            System.out.print(path[i][j] == 1 ? "●" : "○");
        }
        System.out.println();
    }
} else {
    System.out.println("没有找到路径！");
}

该代码输出的结果为：

找到了一条路径：
●○○○○
●●●●○
○○○○●
○○●●●
○○○●○

我们可以看到，除了障碍以外，路径上的所有格子都被标记为 1，表示已探测过的路径。

示例2

下面是另一个迷宫的例子：

0011010
0001011
0110001
1100100
0010111
1010001

起点为 (0, 0)，终点为 (5, 6)。同样可以通过下面的代码来寻路：

int[][] maze2 = {{0, 0, 1, 1, 0, 1, 0},
                 {0, 0, 0, 1, 0, 1, 1},
                 {0, 1, 1, 0, 0, 0, 1},
                 {1, 1, 0, 0, 1, 0, 0},
                 {0, 0, 1, 0, 1, 1, 1},
                 {1, 0, 1, 0, 0, 0, 1}};
int[][] path2 = new int[maze2.length][maze2[0].length];
if (findPath(0, 0, maze2, path2)) {
    System.out.println("找到了一条路径：");
    for (int i = 0; i < path2.length; i++) {
        for (int j = 0; j < path2[0].length; j++) {
            System.out.print(path2[i][j] == 1 ? "●" : "○");
        }
        System.out.println();
    }
} else {
    System.out.println("没有找到路径！");
}

运行结果为：

找到了一条路径：
●●○○○○●
○●○○○○●
○●●○○●●
●●●○●○○
○○●○●●●
●○●○○○●

同样可以看到，除了障碍以外，路径上的所有格子都被标记为 1，表示已探测过的路径。