问题 3636 --单词搜索

3636: 单词搜索

时间限制: 1 Sec  内存限制: 256 MB
提交: 32  解决: 10
[提交][状态][讨论版][命题人:]

题目描述

给定一个 R×C的大写字母矩阵。

请你在其中寻找目标单词 W。

已知，目标单词 W 由若干个不同的大写字母构成。

目标单词可以遵循以下两种规则，出现在矩阵的水平、垂直度线段中：

  • 单词出现在一条线段上。
  • 单词出现在两条相互垂直且存在公共端点的线段上。也就是说，单词首先出现在某线段上，直到某个字母后，转向 90 度，其余部分出现在另一条线段上。

具体可以参照图例。

请你计算，目标单词在给定矩阵中一共出现了多少次。


输入

第一行包含一个由若干个不同的大写字母构成的字符串，表示单词 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 次，如下图所示。







QQ截图20230822172449.png







样例2解释



目标单词一共出现 44 次，如下图所示。


QQ截图20230822172559.png






数据范围



2≤|W|≤6,

1≤R,C≤100

来源

dfs 

[提交][状态]