P3804. 找到它

解题思路

注意，本题和 经典题型. 单词搜索 几乎完全一致，唯一的区别在于前者只要求判断是否能够找到该单词，本题还需要输出起始位置。

状态更新和回滚写在横向遍历 for 循环内的回溯写法

我们需要思考的是，对于这种二维网格如何进行回溯？换句话说，如何构建回溯函数？

在回溯过程中我们需要知道以下信息：

• 当前进行到了单词中的哪一个字符？
• 当前在网格中搜索到了哪一个位置？
• 由于网格中的字符不能重复使用，那么哪一些字符是已经使用过的？
• 是否已经在网格中找到了这个单词？

对于第一点，我们的回溯函数中需要存在参数 word_idx，来表示待搜索的单词此时遍历到的索引位置。 对于第二点，我们的回溯函数需要传入当前搜索的点的位置 (x, y)。 对于第三点，这个在二维网格类型的搜索问题中是非常常用的技巧，即构建一个大小和 grid 一样的 check_list。 对于第四点，我们可以直接声明一个全局变量 isFind 来表示是否已经找到该单词。

除了这些参数之外，我们还需要传入二维矩阵 grid 本身，它的大小 N 和 M 等等。

容易构建出回溯函数如下：

容易发现，此处回溯函数的写法，和我们用 DFS 做二维网格搜索类型的题目是非常类似的。 换句话说，在当前点 (x, y) 的近邻点上下左右四个方向的选取的这个 for 循环，实际上就对应着回溯过程中状态树的横向遍历。 和常规 DFS 解法的区别在于，我们现在搜索的是一条路径，所以我们需要在递归调用 backtracking() 函数的前后，进行 check_list[nx][ny] 的状态更新和回滚，来表示近邻点 (nx, ny) 已经被使用过以及回滚之后再次可以被使用的情况。

在递归调用回溯函数的时候，我们需要将下一个点 (nx, ny) 以及 word 的下一个字符索引 word_idx+1 传入函数中。

回溯的终止条件也非常简单，就是当 word_idx 已经等于 len(word)-1 了，说明整个 word 的所有字符都能够在二维网格中找到，那么修改 isFind 为 True，同时退出搜索。

而递归入口则需要这样调用：

注意到，由于在回溯函数中修改 check_list 始终是对 (nx, ny) 进行修改，所以我们在做起始点搜索的双重循环的时候，在递归函数入口处，需要对起始点 (i, j) 额外地进行 check_list 的状态更新和回滚。

状态更新和回滚写在横向遍历 for 循环外的回溯写法

如果你想直接修改 check_list[x][y] 而不是修改 check_list[nx][ny]，那么回溯函数也可以改成这样：

这样就跟常规的 DFS 解法更加接近，但和常规的回溯题目的相似性就没那么高了。 因为状态更新和回滚写在了横向遍历 for 循环的外部。

对应的，由于此处状态的是 (x, y) 而非 (nx, ny)，那么在递归入口处就可以不用单独进行 (i, j) 的更新了。即递归入口可以写为：

复杂度分析

• 设网格为 N 行 M 列，待搜索单词长度为 L。
• 外层双重循环枚举起点，共 N × M 个候选；只有格子字符等于 word[0] 才会真正进入回溯。
• 每次回溯从当前格子向四个方向尝试，但 check_list 会挡住已在当前路径上的格子（至少来路那一格必被挡住），因此每层实际最多产生 3 个有效分支；递归深度不超过 L，单个起点的搜索代价上界为 O(3^L)。
• 总时间复杂度为 O(N × M × 3^L)，这是最坏情况上界；实际运行中大量分支会因「下一格字符不匹配」提前终止，远达不到该上界。找到答案后 isFind 置真并双层 break，后续起点不再搜索。
• 空间复杂度为 O(N × M + L)：check_list 占 O(N × M)，递归栈深度最多为 L。