题目内容

给定一个大小为 $m \times n$ 的二维字符网格 board 和一个字符串 word。请判断是否可以从网格中选取一系列单元格，使得按访问顺序将这些单元格内的字符依次拼接后，恰好得到 word。

选取单元格时必须满足以下规则：

• 相邻两个单元格必须在网格中水平相邻或垂直相邻；
• 同一个单元格在整个路径中不允许被重复使用。

如果存在这样一条合法路径，返回 true；否则返回 false。

约束条件：

• 网格的行数 m 和列数 n 均满足 $1 \le m, n \le 6$。
• 字符串 word 的长度满足 $1 \le \text{word.length} \le 15$。
• board 和 word 仅由大小写英文字母组成。

输入描述

输入包含两个参数：

• 一个二维字符列表 board，表示给定的字符网格，其中 board[i][j] 表示第 i 行第 j 列的字符；
• 一个字符串 word，表示需要查找的单词。

输出描述

返回一个布尔值。如果可以在网格中找到一条满足相邻移动且不重复使用单元格的路径，使得路径上的字符依次拼接为 word，则返回 true；否则返回 false。

样例1

输入

2 2
A B
C D
ABDC

输出

true

说明

从第 0 行第 0 列的 A 出发，向右到第 0 行第 1 列的 B，向下到第 1 行第 1 列的 D，再向左到第 1 行第 0 列的 C。路径上的字符依次为 A、B、D、C，与 word 完全一致，且没有重复使用单元格，因此返回 true。

样例2

输入

1 1
A
A

输出

true

说明

网格只有 1 行 1 列，字符为 A。单词 word 也是单个字符 A，起点字符匹配且路径不需要移动，因此返回 true。

样例3

输入

3 3
A B C
D E F
G H I
ABEBC

输出

false

说明

从第 0 行第 0 列的 A 出发，向右到第 0 行第 1 列的 B，再向下到第 1 行第 1 列的 E。此时已匹配前缀 ABE，下一个目标字符是 B。

E 的相邻单元格中，B 所在位置已经在路径中使用过，不能被重复访问；其他相邻字符为 D、F、H，都不是 B。因此这条路径无法继续，最终返回 false。