# 老鼠走迷宫与回溯

老鼠走迷宫是在网格上寻找从入口到出口的路径。回溯法沿一条路走到底，遇到死路就退回上一个分叉，换方向再试。本页说明迷宫的表示、四个方向的搜索顺序、访问标记和失败标记，并给出完整实现。回溯的逐层调用与返回依赖[递归](/knowledge/cs/algorithms/recursion/)；若要找最短路径或比较不同路径的代价，应改用广度优先搜索或最短路径算法，而不只是找一条可行路径。

## 定义

**回溯法**按顺序尝试候选解：选择一个候选后递归进入下一层；若沿这个选择无法到达目标，就放弃它，回到上一层尝试下一个候选。与单纯递归枚举的区别是失败后要处理这个候选留下的状态——恢复原状，或标记为已确认不可行，让其他分支能在正确的局面上继续。

用二维列表`m`表示迷宫，每个格子取以下值之一：

* `0`：可以走的格子；
* `1`：墙；
* `2`：当前路径上的格子，进入时标记；
* `3`：已经确认从这里走不到出口的格子，回溯时标记。

入口是 `(sta1, sta2)`，出口是 `(fsh1, fsh2)`。每一步只能走上、下、左、右四个相邻格子，不能斜走。

## 性质

### 搜索步骤

1. **标记当前格子**

   进入 `(i, j)` 后先令`m[i][j] = 2`，表示这个格子已经访问，防止搜索绕回自己。

2. **检查是否到达出口**

   若 `(i, j)` 就是出口，令全局标志`success = 1`，随后逐层返回。

3. **按固定顺序尝试四个方向**

   依次检查上、下、左、右。若相邻格子为0且尚未找到出口，就递归进入该格子。

4. **失败则标记并返回**

   四个方向都没有找到出口时，把`m[i][j]` 改为3，表示从这里出发走不通，再返回上一层。

### 标记的作用

`2`和`3`都让格子不再以0的身份被再次进入，但含义不同：

* `2`是当前搜索路径的一部分。搜索还在进行时，它阻止回到路径上的格子，避免在环里无限递归。
* `3`是已经验证过的死路。从别的方向到达同一个格子，结果仍然是走不通，所以可以直接跳过。

> [!NOTE]
> 把死路标成3之所以正确，是因为“从某个格子出发能否到达出口”只取决于这个格子的位置，与怎样到达它无关。如果问题还要求收集钥匙、不能重复经过某类格子，状态就不止位置一个，不能只用一个3表示失败。

### 找到一条路径就停止

`success`是全局标志。一旦某次递归到达出口，其余方向不再尝试，所有调用依次返回。这样得到的是一条可行路径，不保证最短。若要找最短路径，应使用按层扩展的广度优先搜索；若要枚举所有路径，失败后必须把格子恢复为0，而不是标成3。

### 边界与代价

代码依赖迷宫最外圈全是1：向上、向左越界时，Python的负索引取到的是另一侧的墙；向下越界不会发生，因为最底行是墙，搜索不会进入；这个迷宫的最右列除出口外都是墙，而到达出口后`success`已经置1，后续方向检查被短路。

> [!CAUTION]
> 这个写法依赖外圈完整的一圈墙，并且依赖出口到达后立即把`success`置1。换一份迷宫、移动出口或让外圈出现缺口时，必须显式检查下标范围；否则正方向越界会抛出`IndexError`，负方向可能绕到迷宫另一侧。

每个格子最多被访问一次，时间复杂度为 $O(rc)$（$r$ 行、$c$ 列）；递归深度最多等于路径长度，最坏情况下为 $O(rc)$，大迷宫可能超过Python的默认递归深度。

## 例子

**完整实现：找到一条通路**

```python title="maze-backtracking.py"
m = [
    [1, 1, 1, 0, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 0, 0, 0, 0, 0, 1, 1],
    [1, 0, 1, 1, 1, 1, 1, 0, 0, 1],
    [1, 0, 1, 0, 0, 0, 0, 1, 0, 1],
    [1, 0, 1, 0, 1, 1, 0, 0, 0, 1],
    [1, 0, 0, 1, 1, 0, 1, 0, 1, 1],
    [1, 1, 1, 1, 0, 0, 0, 0, 1, 1],
    [1, 0, 0, 0, 0, 1, 1, 1, 0, 0],
    [1, 0, 1, 1, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
]

sta1 = 0
sta2 = 3
fsh1 = 7
fsh2 = 9
success = 0


def LabyrinthRat():
    print("显示迷宫：")
    for i in range(len(m)):
        print(m[i])
    print("入口：m[%d][%d]：出口：m[%d][%d]" % (sta1, sta2, fsh1, fsh2))
    if (visit(sta1, sta2)) == 0:
        print("没有找到出口")
    else:
        print("显示路径：")
        for i in range(10):
            print(m[i])


def visit(i, j):
    m[i][j] = 2
    global success
    if (i == fsh1) and (j == fsh2):
        success = 1
    if (success != 1) and (m[i - 1][j] == 0):
        visit(i - 1, j)
    if (success != 1) and (m[i + 1][j] == 0):
        visit(i + 1, j)
    if (success != 1) and (m[i][j - 1] == 0):
        visit(i, j - 1)
    if (success != 1) and (m[i][j + 1] == 0):
        visit(i, j + 1)
    if success != 1:
        m[i][j] = 3
    return success


if __name__ == "__main__":
    LabyrinthRat()
```

程序结束后，`m`中值为2的格子连成从入口到出口的路径，值为3的格子是搜索过程中试过但走不通的分支。对这个迷宫，路径从 `(0,3)` 进入，先向下再向右，绕过若干死路后到达 `(7,9)`。

> [!TIP]
> 把四个`if`的检查顺序换掉，得到的仍然是一条通路，但路径形状和访问过的死路会不同。搜索顺序只影响先找到哪一条路径，不影响“是否存在路径”的结论。

`LabyrinthRat`输出路径时的`range(10)` 与迷宫行数绑定；换一份尺寸不同的迷宫，这个数字要一起改。

## 交互探索

逐步查看搜索如何进入相邻格子、在死路回退，并保留访问标记。

交互演示：走到死路后，搜索怎样回退？。逐步观察深度优先搜索在迷宫中的访问和回溯。 请在站点操作演示。

## 练习

1. 在迷宫的标记中，3表示什么？

   * A.  当前路径上的格子
   * B.  已经确认从这里走不到出口的格子
   * C.  墙
   * D.  尚未访问的格子

   答案：B

   进入格子时标2；四个方向都失败后改成3，表示这个格子出发无解。

2. 为什么要在进入格子后立刻令`m[i][j] = 2`？

   * A.  让后续搜索不会再次进入这个格子，避免在环上无限递归
   * B.  为了统计迷宫中有多少个可走格子
   * C.  为了把墙也标记成路径
   * D.  为了让出口的值变成1

   答案：A

   标记后该格子不再是0，其他分支不会再次递归进入它；如果没有标记，两个相邻空格会互相调用，搜索无法终止。

3. 对例子中的迷宫，从入口 `(0,3)` 出发，程序最终能否到达出口 `(7,9)`？

   * A.  能
   * B.  不能

   答案：A

   迷宫中存在一条通路，程序会找到它并令`success = 1`。

4. 找到出口后，全局变量`success`的值是 \_\_\_\_\_\_（success）。

   答案：1

   到达出口时执行`success = 1`，后续调用据此停止尝试其他方向。

5. 如果要求从入口到出口的最短路径，应该改用哪种搜索？

   * A.  按层扩展的广度优先搜索
   * B.  继续用当前的回溯顺序，找到的第一条路径就是最短的
   * C.  把四个方向的检查顺序反过来
   * D.  把死路标记从3改成0

   答案：A

   回溯只保证找到一条可行路径；搜索顺序不影响路径长度，第一条找到的路径不一定最短。广度优先搜索按步数从少到多扩展，第一次到达出口时的路径最短。