题目内容

给定一个 $m \times n$ 的二维字符网格 board 和一个字符串单词 word。

请计算单词 word 在网格中出现的总次数。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个搜索路径中不允许被重复使用。

输入描述

• board：二维字符列表，每个元素为大写英文字母，$1 \le m, n \le 10$。
• word：字符串，由大写英文字母组成，$1 \le \text{len}(\text{word}) \le 100$。

输出描述

• 返回一个整数，表示单词在网格中出现的路径总数。

样例1

输入

[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]],"ABCCED"

输出

1

说明

解释：路径仅如下（仅一条）：

$\text{A} \rightarrow \text{B} \rightarrow \text{C} \rightarrow \text{C} \rightarrow \text{E} \rightarrow \text{D}$

$(0,0)\rightarrow(0,1)\rightarrow(0,2)\rightarrow(1,2)\rightarrow(2,2)\rightarrow(2,1)$

样例2

输入

[["A","A"]],"A"

输出

2

说明

解释：网格中有两个 'A'，每个都可以独立构成单词 "A"，共 $2$ 条路径。

样例3

输入

[["A","B"],["C","D"]],"ABCD"

输出

0

说明

解释：由于单词必须通过水平相邻或垂直相邻的单元格构成，导致 'B' 无法直接与 'C' 构成单词，所以网格中不存在 "ABCD" 的单词路径。