传统题 1000ms 128MiB

Word Search

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

背景

最近,Kepy 迷上了《Undertale》,并试图打完这个游戏的和平线。在和平线中,Kepy 将与怪物们成为朋友。在雪域中,Kepy 遇到了 Sans 和 Papyrus。Sans 和 Papyrus 为了抓捕 Kepy,给 Kepy 设下了重重谜题!现在,Sans 拿出一个谜题试图阻拦 Kepy。

image

说明

如你所见,Sans 会给出一个 nnmm 列的表格,表格上的每一个地方都有一个字母。接着,Sans 给出 qq 个询问,让 Kepy 在表格上寻找这个单词。由于 Kepy 迟迟无法解决这一谜题,Sans 便化简了游戏规则:对于每个单词,Kepy 只需要判断这个单词是否在表格中出现过。

如果以下情形出现,则判定一个长度为 lenlen 的单词 ss 存在于表中:存在一条长度为 lenlen 的路径,其由 lenlen 个点组成,其中第 ii 个点为 (xi,yi)(x_i,y_i),表示表格中第 xix_i 行,第 yiy_i 列上的点。对于这条路径:

  1. 路径上没有重复的点出现。
  2. 对于路径上的第 ii 个点,其在表中对应的字母为单词 ss 的第 ii 个字母,但是 不区分大小写。比如,单词中的第 ii 个字母是 aa,其在表格中对应的字母可以是 AAaa
  3. 对于第 ii 个点 (2ilen)(2 \leq i \leq len),其应该由第 i1i-1 个点向其相邻的一格走到。更形式化的说,max(abs(xixi1),abs(yiyi1))=1\max(abs(x_i-x_{i-1}), abs(y_i-y_{i-1}))=1

例如:对于图片中的单词 "fall\mathtt{fall}",你可以找到一条路径:$(1, 5) \rightarrow (2, 4) \rightarrow (3, 3) \rightarrow (4, 2)$ 来满足上述三点要求,我们就认为 fall\mathtt{fall} 存在于表格上。

即便好心的 Sans 已经化简了游戏规则,Kepy 还是无法解决这一谜题。所以 Kepy 找聪明的 O神 帮忙解决了这个问题,并完成了这一谜题。

现在,O神 想要考考同样聪明的你,让你来帮 Kepy 解决这一谜题。现在,你得到了一个 nnmm 列的只由大写字母组成的表格,和 qq 个询问的单词。对于每个询问,如果其存在于表格中,请输出 Yes,否则,请输出 No

输入格式

第一行给定三个整数 n,m,qn, m, q

接下来共有 nn 行,每行给定一个长度为 mm 的字符串,代表这个表格。

接下来共有 qq 行,每行有一个单词,分别对应每个询问。

输出格式

对于每个询问,如果其存在于表格中,请输出 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

提示

1n×m100,1q101 \leq n \times m \leq 100, 1 \leq q \leq 10

1len51 \leq len \leq 5(其中,lenlen 为每个单词的长度单词长度)。

保证给定的字符串都由大小写字母组成。

FJNU·ACM-23级新手村の第四场世纪大战 (重现赛)

未参加
状态
已结束
规则
ACM/ICPC
题目
12
开始于
2023-10-28 22:30
结束于
2024-3-30 6:30
持续时间
3680 小时
主持人
参赛人数
26