问题陈述
有一个网格 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