📑 本页目录（点开跳转）
06 · 回溯与矩阵：试完一条路怎么干净回来
⏱ 10 分钟 ｜ 矩阵路径、机器人范围、排列
🎯 一句话
回溯的关键动作不是“递归调用”，而是：做选择 → 向下试 → 撤销选择。
🧩 题 1：矩阵中的路径
从每个格子尝试；当前字符匹配才继续走四个方向。一个格子在当前路径中不能重复使用，所以进来标记、离开还原。
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
🧩 题 2：机器人的运动范围
条件变成“坐标位数之和不超过阈值”。能走到一个格子后，再向四周扩展；已经访问过就不用重算。
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
🧩 题 3：字符串的排列
每一层决定当前位置放谁；同一层遇到重复字符时跳过，避免产生重复排列。
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']
🔗 这一章连到哪里
| 去哪 | 为什么 |
|---|---|
| 不靠数据的 AI 14 · 回溯与约束传播 | ⭐ 同一个回溯骨架换个用途：那一章拿它解约束满足问题，并且往上加了两件本章没有的东西 —— 前向检查「看一步就知道前面有墙」、弧相容「还没走就知道整片区域是墙」 |
🛑 可以停在这里
回溯题写不出来时，检查有没有成对出现：标记/还原、加入/移除、选择/撤销。
✅ 检查点
矩阵路径题为什么必须恢复 board[r][c]？
👀 看答案
这个格子只是当前分支不能再用；别的起点或兄弟分支仍应可以用它。恢复现场才能让下一条路独立尝试。
⚡ 走神救援
- 回溯三拍：选择、递归、撤销。
- 路径题要防止当前路径重复用格子。
- 排列去重：同一层相同字符只尝试一次。