第7章｜回溯与搜索
Unit 08 · LeetCode #79 · 优化版
← Unit 07
79
Word SearchGrid DFS · Visit · Restore
路径从线性区间，
扩展到二维网格的四邻域。
进入 dfs(row,col,index) 时，当前位置尝试匹配 word[index]。匹配后临时占用格子，只向上下左右扩展；无论分支成功或失败，返回调用者前都要恢复该格子。
LeetCode #79 题目模型四邻接路径，同一坐标在一条路径中只能使用一次
题目要求
给定字符网格 board 和字符串 word，判断能否从某个格子开始，通过水平或垂直相邻格子依次构造出该单词。
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
pass
主实验
- 网格为官方示例；
- 主路径构造
ABCCED； - 恢复实验使用
SEE的失败起点。
状态契约
state = (row, col, index)
candidate = four neighbors
path chars = word[:index+1]
current cell matches word[index]
coordinates are unique in current path
restore before return
章节联系
Unit 07 的下一状态只有 end+1；本题每个状态最多产生四个空间后继，因此必须新增“路径内占用”状态。
Spatial State
递归状态由二维坐标和单词下标共同定义，候选来自当前格子的四邻域。
Character Alignment
一个坐标只有在字符等于当前目标字符时，才会被标记并进入更深递归。
Path-Local Visit
占用只属于当前调用链；失败分支访问过的格子不能永久封锁其他路径。
Restore on Return
先保存原字符，再临时标记；递归结束后恢复，保持父调用看到的网格不变。
1. 二维四邻接
2. 字符与占用过滤
3. 失败后恢复
4. 路径占用反例
5. 槽位＋真实轨迹
6. 迁移 #212
已恢复上次学习位置、代码槽位和运行轨迹。
board · word="ABCCED"四邻接，不允许重复坐标
目标单词进度
当前坐标路径
当前四邻居
路径内占用
当前搜索链
为什么当前动作安全
当前递归契约
搜索事件
当前坐标
word index
下一字符
路径长度
候选范围上下左右
完成条件index == len(word)
路径不变量
恢复不变量
已匹配字符
当前路径长度
已占用格子
有效下一步
状态一致
1. 完整演示
2. 功能提示槽位
3. 关键代码补全
4. 独立完成
关键槽位补全先选语义槽位 → 再选代码
待填槽位｜只提示作用
待选代码｜顺序随机
实时拼接后的代码骨架0 / 6
当前认知焦点1 / 1
真实 DFS 调用树
代码 × 状态逐行联动board / visited / current 同步
状态依赖问题｜不阻塞逐行运行
成功的 goal 子调用已经返回 True，但当前父帧的格子仍被临时标记为 #。父帧真正 return found 之前必须先做什么？
独立完成：关闭上方脚手架后，只保留完整编辑器。
#79 独立完成
迁移题：LeetCode #212 单词搜索 II
空间 DFS 的四邻接、路径内占用与恢复保持不变；固定 word[index] 改为 Trie 当前节点的允许后继字符。前缀不在 Trie 中时立即结束该调用。
Unit 08 完成
二维网格回溯的核心是：用坐标和匹配进度定义状态，只扩展四邻居；把格子占用限制在当前调用链，并在函数返回前恢复，从而保证不同起点和兄弟分支互不污染。
题型#79｜二维路径匹配
状态row、col、index、路径占用
候选上下左右四邻居
过滤越界、字符不匹配、当前路径已占用
选择临时标记当前格子
完成index == len(word)
恢复返回前还原原字符
作用域visited 属于当前路径，不是全局永久状态
迁移#212：Trie 前缀节点替代固定 word index