← 返回题目列表

AtCoder · past17_g

G. 蜿蜒的字符串

中文机器翻译题面 查看原题

问题陈述

有一个网格 H 水平行和 W 垂直列。我们表示为 (i,j) 中的单元格 i从顶部开始的第行和 j左起第 列。
每个单元格上都写有一个小写英文字母。信上写着 (i, j) is G_{i, j}.
给你一个字符串 S 长度 N。是否存在细胞序列 (a_1, b_1), (a_2, b_2), \dots, (a_N, b_N) 满足以下条件?打印 Yes 如果有,并且 No 否则。

  • (a_1, b_1), (a_2, b_2), \dots,和 (a_N, b_N) 成对不同。
  • (a_i, b_i) 和 (a_{i+1}, b_{i+1}) 在八个方向之一上相邻。 \max(\vert a_i - a_{i+1} \vert, \vert b_i - b_{i+1} \vert) = 1.
  • 这封信写在 (a_i, b_i) 与 i- 第一个字符 S.

约束

  • 1 \leq H, W \leq 10
  • G_{i, j} 是一个小写英文字母。
  • 1 \leq N \leq 5
  • S 是一个长度-N 由小写英文字母组成的字符串。

输入

输入由标准输入按以下格式给出:

H W
G_{1,1}G_{1,2}\dots G_{1,W}
G_{2,1}G_{2,2}\dots G_{2,W}
\vdots
G_{H,1}G_{H,2}\dots G_{H,W}
N
S

输出

打印 Yes 如果存在一致的细胞序列;打印 No 否则。


示例输入 1

3 3
ekz
sza
znz
5
snake

示例输出 1

Yes

细胞序列 (2, 1), (3, 2), (2, 3), (1, 2), (1, 1) 满足问题陈述中的所有条件,所以答案是 Yes.


示例输入 2

2 5
qwert
asdfg
4
awrg

示例输出 2

No

示例输入 3

3 3
abc
zbc
zzc
5
abcba

示例输出 3

No