#P2304G. Word Search
Word Search
背景
最近,Kepy 迷上了《Undertale》,并试图打完这个游戏的和平线。在和平线中,Kepy 将与怪物们成为朋友。在雪域中,Kepy 遇到了 Sans 和 Papyrus。Sans 和 Papyrus 为了抓捕 Kepy,给 Kepy 设下了重重谜题!现在,Sans 拿出一个谜题试图阻拦 Kepy。
说明
如你所见,Sans 会给出一个 行 列的表格,表格上的每一个地方都有一个字母。接着,Sans 给出 个询问,让 Kepy 在表格上寻找这个单词。由于 Kepy 迟迟无法解决这一谜题,Sans 便化简了游戏规则:对于每个单词,Kepy 只需要判断这个单词是否在表格中出现过。
如果以下情形出现,则判定一个长度为 的单词 存在于表中:存在一条长度为 的路径,其由 个点组成,其中第 个点为 ,表示表格中第 行,第 列上的点。对于这条路径:
- 路径上没有重复的点出现。
- 对于路径上的第 个点,其在表中对应的字母为单词 的第 个字母,但是 不区分大小写。比如,单词中的第 个字母是 ,其在表格中对应的字母可以是 或 。
- 对于第 个点 ,其应该由第 个点向其相邻的一格走到。更形式化的说,。
例如:对于图片中的单词 "",你可以找到一条路径:$(1, 5) \rightarrow (2, 4) \rightarrow (3, 3) \rightarrow (4, 2)$ 来满足上述三点要求,我们就认为 存在于表格上。
即便好心的 Sans 已经化简了游戏规则,Kepy 还是无法解决这一谜题。所以 Kepy 找聪明的 O神 帮忙解决了这个问题,并完成了这一谜题。
现在,O神 想要考考同样聪明的你,让你来帮 Kepy 解决这一谜题。现在,你得到了一个 行 列的只由大写字母组成的表格,和 个询问的单词。对于每个询问,如果其存在于表格中,请输出 Yes
,否则,请输出 No
。
输入格式
第一行给定三个整数 。
接下来共有 行,每行给定一个长度为 的字符串,代表这个表格。
接下来共有 行,每行有一个单词,分别对应每个询问。
输出格式
对于每个询问,如果其存在于表格中,请输出 Yes
,否则,请输出 No
。
输出大小写不敏感,如果答案为 Yes
,那么诸如 YES
, yEs
都能通过。
样例
样例输入1
6 16 5
GIASFCLFUBREHBER
NPBAVUUJJCSEOMEO
IWLSNOTELEKSTMFB
RLXETMONSTERMNGO
PMDIAMREMAUUJHIT
SCIGARSUXRSOUDCW
fall
Under
tale
Kepy
Robot
样例输出1
Yes
No
No
No
Yes
提示
(其中, 为每个单词的长度单词长度)。
保证给定的字符串都由大小写字母组成。