CJDF06｜字母路径 题解

核心算法

枚举起点，用 DFS 匹配单词的下一个字符，并在返回时恢复访问标记。

思路推导

状态为 (x,y,pos)：当前位于 (x,y)，正在匹配 word[pos]。字符不等立即失败；匹配末字符立即成功。继续搜索前标记当前格，返回前取消标记，使它能被其他路径使用。

正确性说明

算法枚举所有可能起点，并从每个状态枚举所有合法下一步，因此不会漏掉任何简单路径。访问标记保证同一路径不重复用格；回溯恢复保证不同候选路径互不影响。

复杂度

最坏时间复杂度 $O(nm\cdot4^{|word|})$，空间复杂度 $O(nm+|word|)$。题目规模按搜索算法设置。

易错点

• 访问标记属于“当前路径”，返回时必须恢复；
• 末字符匹配成功后立即返回；
• 不能斜向移动，也不能重复使用同一格。