给定一个 R×C的大写字母矩阵。
请你在其中寻找目标单词 W。
已知，目标单词 W 由若干个不同的大写字母构成。
目标单词可以遵循以下两种规则，出现在矩阵的水平、垂直度线段中：
- 单词出现在一条线段上。
- 单词出现在两条相互垂直且存在公共端点的线段上。也就是说，单词首先出现在某线段上，直到某个字母后，转向 90 度，其余部分出现在另一条线段上。
具体可以参照图例。
请你计算，目标单词在给定矩阵中一共出现了多少次。
问题 D: 单词搜索
时间限制: 1 Sec 内存限制: 256 MB提交: 32 解决: 10
[提交][状态][讨论版][命题人:]
题目描述
输入
第一行包含一个由若干个不同的大写字母构成的字符串，表示单词 W。
第二行包含整数 R。
第三行包含整数 C。
接下来 R 行，每行包含 C个大写字母，表示给定字母矩阵。
输出
一个整数，表示目标单词在给定矩阵中的出现次数。
样例输入
样例1：
MENU
5
7
F T R U B L K
P M N A X C U
A E R C N E O
M N E U A R M
M U N E M N S
样例2：
NATURE
6
9
N A T S F E G Q N
S A I B M R H F A
C F T J C U C L T
K B H U P T A N U
D P R R R J D I R
I E E K M E G B E样例输出
样例1
3
样例2
4提示
样例1解释
目标单词一共出现 33 次，如下图所示。
样例2解释
目标单词一共出现 44 次，如下图所示。
数据范围
2≤|W|≤6,
1≤R,C≤100