单词搜索
Word Search
在网格中判断是否存在一条路径，按顺序拼出给定单词；路径只能上下左右走，不能重复用格。
在力扣中练习题目描述
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例 1：
输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCCED" 输出：true
示例 2：
输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "SEE" 输出：true
示例 3：
输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCB" 输出：false
提示：
m == board.lengthn = board[i].length1 <= m, n <= 61 <= word.length <= 15board和word仅由大小写英文字母组成
进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？
解题思路
DFS + 原地标记
匹配一个字符就占住格子，失败时恢复
从每个格子出发尝试匹配 word[0]，匹配成功就向四个方向递归匹配下一个字符。
已经走过的格子不能在当前路径中再次使用。最省空间的做法是把它临时改成 '#'，递归返回时再恢复原字符；这样不需要额外的 visited 矩阵。
匹配第 0 个字符 H，进入 (1,0)。
- k
- 0
自拟网格中的 HORSE 需要向右走三步、再向上拐一次。方向顺序不重要，但每个方向失败后都必须恢复当前格，否则其他路径会被错误地挡住。
匹配第 3 个字符 S，进入 (1,3)。
- k
- 3
每个起点做一次 DFS，单次最多 4^L 条路径，总时间 O(m·n·4^L)，递归深度 O(L)。
易错点
- 失败后忘记恢复字符：后续起点无法使用这一格。
- 只向两个方向搜索：漏掉向上/向左的路径。
- 没有越界检查就取 board[r][c]：会访问非法内存。
- 认为起点必须在 (0,0)：单词可以从任意位置开始。
DFS + visited 矩阵
单独开一个布尔矩阵记录当前路径
逻辑等价，额外 O(m·n) 空间；原地标记版把访问状态复用到了棋盘上。
如果不想修改输入棋盘，可以开一个 used 矩阵，进入格子时设为 true，回退时设为 false。
它的可读性更好：棋盘数据和访问状态分离，调试时能直接看到哪些格子在当前路径上。代价是 O(m·n) 额外空间。
当棋盘不能被修改，或者需要同时保留多个搜索状态时，visited 矩阵更合适；否则原地标记更省空间。
- 1建立与棋盘同尺寸的 used。
- 2进入格子前检查 used。
- 3递归前置 true，失败后置 false。
- 4其余与原地标记相同。
易错点
- used 只置 true 不恢复：所有路径共享了错误的访问历史。
- 把 used 按值传参：每次递归复制整张矩阵，复杂度爆炸。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
board = [["W","A","T","E"],["H","O","R","S"],["L","I","N","E"],["D","R","A","M"]]，word = "HORSE"要从网格中找 "HORSE"，可以向上下左右走，但不能斜走或重复经过同一格。
查看 C++ 代码
延伸阅读
- 网格搜索的“已访问”是路径级状态，不是全局状态；回溯时必须撤销。
- 如果单词很长，可以先统计字符频次，棋盘不足时直接返回 false。