📑 本页目录(点开跳转)
06 · 回溯与矩阵:试完一条路怎么干净回来
⏱ 10 分钟 | 矩阵路径、机器人范围、排列
🎯 一句话
第 02 章试完一条树路径,会弹掉刚加入的节点。现在把这件事放到网格里。走错路时,下一条路需要从同一个分叉重新出发,这就要求我们恢复刚才改动的状态。
回溯(backtracking)沿当前选择深入,再回到分叉继续尝试。每次进入分支时,先弄清返回时哪些记录要恢复。
🧩 题 1:矩阵中的路径
要在一块字母板上拼出 ABBBCB。每一步可向上、下、左、右移动一格,同一条路每个格子最多用一次。第一个字母 A 下面和右边都是 B,先走哪边才接得上?
| 行 | 第 0 列 | 第 1 列 | 第 2 列 |
|---|---|---|---|
| 第 0 行 | A 起点 | B | B |
| 第 1 行 | B 先试 | C | B |
- 先往下。 从 A 到 (1, 0) 的 B。下一字母还是 B,但右边是 C,上面已用过,其余方向越界。这条分支结束。
- 退回 A。 把 (1, 0) 恢复成 B,A 继续留在当前路径里。
- 改往右。 沿右、右、下、左、左拼出 A → B → B → B → C → B。最后一个 B 正是刚才恢复的 (1, 0)。
代码会枚举每个起点。visit(r, c, index) 问的是,在已经用过的格子保持标记时,能否从第 r 行第 c 列匹配目标从 index 开始的剩余部分。越界或字母不符就结束这个尝试,匹配成功才临时把格子记为 #。
def has_path(board, word):
rows, cols = len(board), len(board[0])
def visit(r, c, index):
if index == len(word):
return True
if not (0 <= r < rows and 0 <= c < cols) or board[r][c] != word[index]:
return False
saved, board[r][c] = board[r][c], '#'
found = any(visit(r + dr, c + dc, index + 1) for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)))
board[r][c] = saved
return found
return any(visit(r, c, 0) for r in range(rows) for c in range(cols))
grid = [list('ABCE'), list('SFCS'), list('ADEE')]
assert has_path(grid, 'ABCCED') is True
assert has_path(grid, 'ABCB') is False
index == len(word) 表示所有字符已匹配,这次返回无需再访问新格子。any 遇到第一个成功分支就停止尝试。先保存结果 found,还原格子后再返回。这样成功和失败都会恢复输入。
这段代码约定输入是至少一行一列的矩形,行是可修改的字符列表,目标不含占位符 #。在这个约定下,空目标返回 True。如果需要支持空板或目标含 #,应先定义空板的返回规则,并使用独立的路径标记。
设行数为 R、列数为 C、目标长度为 L,K 取 L 与格子数 R × C 中的较小值。最多有 R × C 个起点。第一步至多四个方向,以后至少有来时的一个格子已用过,至多三个方向能继续深入。算上每层最多四次邻居检查,时间上界为 O(R × C × 3K)。板上标记原地改写,额外空间主要是递归栈,至多 O(K + 1)。
🧩 题 2:机器人的运动范围
机器人从 (0, 0) 出发,只能上下左右逐格走。一个坐标可进入的条件是行号和列号的十进制各位数字之和不超过阈值。例如 (0, 11) 的和是 0 + 1 + 1 = 2。
| 列号 | 数字之和 | 从 0 出发 |
|---|---|---|
| 0、1、2 | 0、1、2 | 依次可达 |
| 3 到 9 | 3 到 9 | 超过阈值 |
| 10、11 | 1 + 0 = 1、1 + 1 = 2 | 符合阈值,但中间断开 |
可达(reachable)表示存在一条从起点出发、每一步都合法的路线。按表手算,机器人到 2 后就无法越过 3,答案是 3 个格子。只数数字和合格的格子会把 10、11 也算进去。
继续用第 02、03 章的栈(stack)存待办,最近放入的坐标最先取出。取到新坐标时先检查边界和数字之和,通过才加入 seen,再把四邻放入栈。一个格子一旦扩展过,从另一条路来时它的邻居仍然相同,因此 seen 保留到本次搜索结束。
def moving_count(rows, cols, limit):
def digit_sum(value):
return sum(map(int, str(value)))
seen, stack = set(), [(0, 0)]
while stack:
r, c = stack.pop()
if (r, c) in seen or not (0 <= r < rows and 0 <= c < cols):
continue
if digit_sum(r) + digit_sum(c) > limit:
continue
seen.add((r, c))
stack.extend(((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)))
return len(seen)
assert moving_count(3, 3, 1) == 3
在代码里,重复候选可能入栈,但同一个可达格子最多扩展一次。令 V 为可达格子数,入栈总次数最多为起点一次加每个可达格子四次。把集合查找按平均常数时间计,令 D 为检查一个坐标的数字和所需的最多操作数,包含转字符串和逐位相加。时间上界为 O((V + 1) × D)。栈和集合最多保存 O(V + 1) 个坐标,求数字和时还要临时保存数字字符串。固定坐标位数时,时间和辅助空间都随可达格子数线性增长。零尺寸或负阈值返回 0,正尺寸且阈值为 0 时只能停在起点。
🧩 题 3:字符串的排列
给三个字母 A、B、A 排座次。选第一张 A 或第三张 A 开头,剩下的字母都有一个 A 和一个 B。这两个选择会产生同一批结果,所以这一层只需试一次 A。
排列(permutation)把所有输入字符用完,顺序不同就产生不同的结果。prefix 是已排好的前缀,rest 是还没排的字符。每个递归调用只负责给当前前缀填一位,并新建局部集合 used,记录这个前缀已经试过的字符。深度相同的不同前缀也各有各的集合。
| 第一位 | 剩下 | 输出 |
|---|---|---|
| 第一个 A | BA | ABA、AAB |
| B | AA | BAA,同层第二个 A 跳过 |
| 最后一个 A | 该层已试过 A | 跳过 |
同一个字母可以在不同位置再次使用。第一位选 A 后,下一层还有自己的 used,因此 AAB 仍能生成。rest 变空时,当前 prefix 就是一项完整答案。
def permutations(text):
answer = []
def choose(prefix, rest):
if not rest:
answer.append(prefix)
return
used = set()
for index, char in enumerate(rest):
if char in used:
continue
used.add(char)
choose(prefix + char, rest[:index] + rest[index + 1:])
choose('', text)
return answer
assert permutations('aab') == ['aab', 'aba', 'baa']
递归时,prefix + char 和切片拼接产生下一层的字符串。父层的两个字符串都保持原样,返回后直接用它们尝试下一个字符。空字符串也直接到达终点,这个实现返回只包含一个空排列的 ['']。
若 n 个字符都不同,第一位有 n 种选法,第二位有 n − 1 种,直到只剩一种,结果数就是 n!(从 n 乘到 1)。例如 A、B、C 有 3 × 2 × 1 = 6 种,A、B、A 经同层去重只有 2 + 1 = 3 种。
三个不同字符的递归,从空前缀到完整排列,各层调用数是 1 + 3 + 6 + 6 = 16。推广到 n 个不同字符,从叶子往上每层分别除以 1、2、3,直到 n。从除以 2 开始,每层调用数至多是上一层的一半,所以各层合计少于 3 × n!。每次调用的循环至多扫 n 个字符,每次向下调用也有 O(n) 的切片和拼接成本,因此最坏时间为 O(n × n!)。沿途至多保存 n + 1 层前缀、剩余字符串和 used,辅助空间为 O(n²)。若实际输出 P 个排列,保存答案另用 O(n × P) 空间(n ≥ 1)。
🔗 这一章连到哪里
| 去哪 | 为什么 |
|---|---|
| 不靠数据的 AI 14 · 回溯与约束传播 | ⭐ 同一个回溯骨架换个用途:那一章拿它解约束满足问题,并且往上加了两件本章没有的东西 —— 前向检查「看一步就知道前面有墙」、弧相容「还没走就知道整片区域是墙」 |
本节回顾
回溯题写不出来时,检查有没有成对出现:标记/还原、加入/移除、选择/撤销。
先写清记录的有效范围。矩阵路径的标记跟着当前路线,机器人的 seen 跟着整次搜索,排列的 used 只在当前前缀的这次调用里有效。下一章仍会用到矩阵坐标,顺时针打印按边界收缩决定下一步。
✅ 检查点
矩阵路径题为什么必须恢复 board[r][c]?
👀 看答案
这个格子只是当前分支不能再用;别的起点或兄弟分支仍应可以用它。恢复现场才能让下一条路独立尝试。
先预测。 两条路线在同一个格子汇合。机器人题为何可以跳过之前处理过的格子,矩阵拼字题却可能要再次尝试?
👀 比较两种访问记录
机器人从同一个格子继续走时,四个方向的合法条件固定。拼字时,匹配到了第几个字符、这条路已经用过哪些格子,都会改变接下来的选择。
再判断。 排列 ABA 时,如果所有层共用一个 used,哪一步会错过 AAB?
👀 检查第二位
第一位选 A 后,第二位还应允许再选剩下的 A。共用集合会把第一位选过的 A 带到第二位,使这个分支被错误跳过。
⚡ 走神救援
- 回溯三拍:选择、递归、撤销。
- 路径题要防止当前路径重复用格子。
- 排列去重:同一层相同字符只尝试一次。