Description

在 CCC 单词搜索游戏中，单词隐藏在一个字母网格中。隐藏单词的字母总是以顺序出现在水平、垂直或对角线段上，有两种方式。一种方式是单词的字母出现在一条线段上。另一种方式是单词的字母出现在一条线段上直到某个字母，然后在该字母处形成直角的第二条线段上。给定一个字母网格和一个要搜索的单词，你的任务是确定该特定单词在网格中隐藏的次数。

Input Format

输入的第一行将包含一个由不同的大写字母组成的字符串 $W$，表示你要在网格中搜索的单词。$W$ 的长度至少为 2。输入的第二行将是一个整数 $R(1 \le R \le 100)$，其中 $R$ 是网格中的行数。输入的第三行将是一个整数 $C(1 \le C \le 100)$，其中 $C$ 是网格中的列数。剩下的输入将提供网格中的字母。它将由 $R$ 行组成，每行包含 $C$ 个用单个空格分隔的大写字母。

Output Format

下表显示了可用的 15 分是如何分配的：

输出将由一个非负整数 $H$ 组成，表示单词在网格中隐藏的次数。

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

3

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

4

Hint

本题采用捆绑测试。

• 子任务 $1$（$2$ 分）：隐藏字符串一定在一条水平线段上。
• 子任务 $2$（$2$ 分）：隐藏字符串一定在一个水平或垂直线段上。
• 子任务 $3$（$2$ 分）：隐藏字符串一定在一个水平、垂直或对角线段上。
• 子任务 $4$（$9$ 分）：隐藏字符串一定在一个线段或两个互相垂直的线段上。

样例 $1$ 图解：

样例 $2$ 图解：

题面翻译由 ChatGPT-4o 提供。