1952: 单词搜索
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：41
Solved：11
Description
给定一个 R×C 的大写字母矩阵。
请你在其中寻找目标单词 W。
已知，目标单词 W 由若干个不同的大写字母构成。
目标单词可以遵循以下两种规则，出现在矩阵的水平、垂直或斜 45 度线段中：
（1）单词出现在一条线段上。
（2）单词出现在两条相互垂直且存在公共端点的线段上。也就是说，单词首先出现在某线段上，直到某个字母后，转向 90 度，其余部分出现在另一条线段上。
具体可以参照图例。
请你计算，目标单词在给定矩阵中一共出现了多少次。
请你在其中寻找目标单词 W。
已知，目标单词 W 由若干个不同的大写字母构成。
目标单词可以遵循以下两种规则，出现在矩阵的水平、垂直或斜 45 度线段中：
（1）单词出现在一条线段上。
（2）单词出现在两条相互垂直且存在公共端点的线段上。也就是说，单词首先出现在某线段上，直到某个字母后，转向 90 度，其余部分出现在另一条线段上。
具体可以参照图例。
请你计算，目标单词在给定矩阵中一共出现了多少次。
Input
第一行包含一个由若干个不同的大写字母构成的字符串，表示单词 W。
第二行包含整数 R。
第三行包含整数 C。
接下来 R 行，每行包含 C 个大写字母，表示给定字母矩阵。
数据范围：
2≤|W|≤6,
1≤R,C≤100
第二行包含整数 R。
第三行包含整数 C。
接下来 R 行，每行包含 C 个大写字母，表示给定字母矩阵。
数据范围：
2≤|W|≤6,
1≤R,C≤100
Output
一个整数，表示目标单词在给定矩阵中的出现次数。
Sample Input Copy
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 SSample Output Copy
3HINT
样例1解释
目标单词一共出现 3 次，如下图所示。
样例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
样例2输出
4
样例2解释
目标单词一共出现 4 次，如下图所示。
目标单词一共出现 3 次，如下图所示。
样例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
样例2输出
4
样例2解释
目标单词一共出现 4 次，如下图所示。