线性动态规划：单词搜索 II 的变种——带方向限制的单词搜索

题目描述
给定一个 m x n 的字符网格 board 和一个单词列表 words，要求找出所有在网格中能够通过相邻单元格（上下左右四个方向，但本题增加方向限制：路径上相邻两步的移动方向不能相同）连接形成的单词，并返回这些单词的列表。

注意

1. 同一个单元格内的字母在一个单词中不允许被重复使用。
2. 相邻两步的移动方向不能相同（例如：上一步向右走，下一步就不能再向右走，必须改变方向）。
3. 单词列表中的每个单词长度至少为 1，且由小写英文字母组成。
4. 你需要返回所有能够在网格中按规则找到的单词，结果可以按任意顺序返回。

示例

board = [
  ['a','b','c'],
  ['d','e','f'],
  ['g','h','i']
]
words = ["abc", "abd", "abed", "abcfi", "abcfihgde"]

可能的输出（具体取决于实际存在情况）：
["abc", "abed", "abcfi"]
解释：

• "abc" 可以沿路径 (0,0)→(0,1)→(0,2) 形成，但注意方向限制：第一步向右（从 a→b），第二步仍向右（b→c），这违反了“相邻两步方向不能相同”的限制，因此此路径不允许。实际上，若想构成 "abc"，必须改变方向，比如 (0,0)→(0,1) 向右，(0,1)→(1,1) 向下，(1,1)→(1,2) 向右？但这样字母顺序不是 "abc"。因此需要仔细搜索。
  实际上，存在一条符合方向限制的路径吗？我们稍后分析。

题目本质是在经典“单词搜索 II”（通常用 Trie + DFS 回溯）的基础上，增加了“相邻两步方向不能相同”的限制条件，这会使得搜索时需要记录上一步的方向，从而避免连续同向移动。

解题思路
这个问题可以分解为两个主要部分：

1. 构建字典树（Trie）：用于高效匹配单词前缀，避免每次搜索都遍历整个单词列表。
2. 深度优先搜索（DFS）回溯：从每个网格单元格出发，尝试构建路径，同时检查方向限制。

我们逐步深入：

步骤 1：理解方向限制对状态的影响
通常的单词搜索 DFS 中，状态包括：当前坐标 (r, c)、当前匹配到单词的第几个字符 idx、以及已访问的单元格集合（通常用 visited 数组标记）。
现在需要增加一个状态：上一步的移动方向 prevDir，用来确保下一步不会选择相同的方向。
初始时，第一步没有“上一步方向”，我们可以用一个特殊值（如 -1）表示起始，此时任何方向都允许。

步骤 2：定义方向数组与状态表示
设四个方向：上(0)、右(1)、下(2)、左(3)，分别对应 dirs = [(-1,0), (0,1), (1,0), (0,-1)]。
在 DFS 函数中，参数：(r, c, idx, prevDir, visited)

• idx 表示当前正在尝试匹配单词中的第几个字符（从 0 开始）。
• prevDir 是上一步的移动方向索引（0~3），初始为 -1。

进入 DFS 后，首先检查当前位置 board[r][c] 是否等于单词的第 idx 个字符。
若相等且 idx == word.length()-1，说明找到了完整单词。
否则，对于下一个字符 word[idx+1]，我们尝试四个方向，但跳过与 prevDir 相同的方向（除非 prevDir == -1）。

步骤 3：DFS 回溯细节

1. 标记当前单元格已访问 visited[r][c] = true。
2. 对于每个可能的新方向 nextDir（0~3）：
   • 如果 nextDir == prevDir，则跳过（方向限制）。
   • 计算新坐标 (nr, nc)。
   • 确保新坐标在网格内且未被访问。
   • 递归调用 DFS，传入 nextDir 作为新的 prevDir，idx+1 作为新的索引。
3. 回溯：取消标记 visited[r][c] = false。

步骤 4：结合字典树优化
因为单词列表可能很大，我们先将所有单词插入字典树。
字典树的节点结构包含：

• children[26]：子节点指针。
• isEnd：标记是否为某个单词的结尾（同时可以存储单词本身或索引）。

在 DFS 时，我们不传递具体单词，而是传递当前字典树节点 node。
从根节点开始，每进入一个单元格 (r, c)，检查 node.children[board[r][c]-'a'] 是否存在：

• 若不存在，直接返回（前缀不匹配）。
• 若存在，移动到该子节点，然后检查 isEnd：如果为真，说明找到了一个单词，将其加入结果集（注意去重，因为可能有多条路径找到同一个单词）。
• 然后继续向四个方向（避开同向）递归搜索。

步骤 5：整体算法流程

1. 构建字典树，插入所有单词。
2. 遍历网格每个位置 (i, j)，作为搜索起点。
3. 从根节点开始，进行 DFS 搜索，传入 prevDir = -1。
4. 收集所有找到的单词（注意去重，比如用哈希集合暂存结果）。
5. 将集合转为列表返回。

步骤 6：时间复杂度分析
设网格大小 m × n，单词列表总长度 L（所有单词字符总数）。

• 建树：O(L)
• 搜索：最坏情况下，每个起点可能展开很多路径，但由于方向限制，路径分支减少（原来4个方向，现在每个位置最多3个方向继续走）。
  但单词长度有限（实际不会太长），所以整体复杂度可以接受。

举例验证
回到开头例子：
单词 "abc" 能否找到？
起点 (0,0) 'a'，第一步向右到 (0,1) 'b'（prevDir=右），下一步不能向右，只能上下左，但 (1,1) 是 'e'，不匹配 'c'，向上越界，向左已访问，因此无法接 'c'。
如果换路径：从 (0,0) 'a' 向下到 (1,0) 'd'（不匹配 'b'）不行。
所以 "abc" 在本规则下无法找到（因为需要连续两个右移，违反了方向限制）。
但 "abed" 可能可以：
(0,0) 'a' → (0,1) 'b'（右）→ (1,1) 'e'（下，方向改变）→ (1,0) 'd'（左，方向改变），符合要求。
所以 "abed" 是可以的。

这样，最终输出会排除那些因方向限制无法构成的单词。

实现提示

• 使用 Trie 节点存储单词在找到时直接记录，避免重复搜索同一单词。
• visited 数组可以用二维布尔数组，也可以复用 board 临时标记为特殊字符（如 '#'）然后回溯恢复。
• 方向检查：if nextDir != prevDir 才继续。
• 去重：同一个单词可能通过不同路径找到多次，用集合存储结果。

这个变种题目在经典单词搜索 II 的基础上增加了方向限制，使得 DFS 状态多了一维，但核心依然是回溯+剪枝+Trie 优化。