QOJ.ac

QOJ

时间限制: 3 s 内存限制: 1024 MB 总分: 100

#3939. 隐藏的单词

统计

Ingrid 正在解决周六报纸上的“网格填字游戏”(Hidden Words in a Grid),但她发现手工完成这项工作有些乏味。幸运的是,Ingrid 会编程,并编写了一个精巧的图像识别程序,可以将谜题图片转换为整洁的文本格式。然而,她在编写实际求解谜题的程序时遇到了困难——你能帮帮她吗?

如果一个单词可以通过从网格中的某个单元格出发,并从那里移动到相邻的未访问单元格来构造,则称该单词包含在 $h \times w$ 的网格中。如果两个单元格相邻(不包括对角线移动),则称它们互为邻居。给定这样一个网格和单词列表,请确定列表中有多少个单词包含在网格中。

输入格式

第一行包含两个整数 $h$ 和 $w$ ($1 \le h, w \le 10$),表示网格的高度和宽度。接下来 $h$ 行,每行包含一个长度为 $w$ 的字符串,由大写字母组成,描述网格的一行。随后一行包含一个整数 $n$ ($1 \le n \le 100\,000$),表示 Ingrid 要查找的单词数量。最后是 $n$ 个单词,每个单词占一行。这些单词的长度均不超过 10 个字符。

输出格式

输出一个整数,表示网格下方给出的单词列表中,有多少个单词包含在网格中。

CC-BY-SA 3.0, Amit6 via Wikimedia Commons

样例

样例输入 1

4 4
SNKO
VRER
IDIN
NEGU
3
KORN
NEDI
DER

样例输出 1

2

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.