/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
問題文
縦 H マス、横 W マスのグリッドがあります。上から i 行目、左から j 列目のマスを (i, j) と呼びます。
各マスには英小文字が書かれています。(i, j) に書かれている文字は G_{i, j} です。
長さ N の文字列 S が与えられます。マスの列 (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}) は 8 方向に隣接している。言い換えると \max(\vert a_i - a_{i+1} \vert, \vert b_i - b_{i+1} \vert) = 1 である。
- (a_i, b_i) に書かれた文字は S の i 文字目と一致する。
制約
- 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
Problem Statement
There is a grid with H horizontal rows and W vertical columns. We denote by (i,j) the cell in the i-th row from the top and j-th column from the left.
Each cell has a lowercase English letter written on it. The letter written on (i, j) is G_{i, j}.
You are given a string S of length N. Is there a sequence of cells (a_1, b_1), (a_2, b_2), \dots, (a_N, b_N) that satisfies the following conditions? Print Yes if there is, and No otherwise.
- (a_1, b_1), (a_2, b_2), \dots, and (a_N, b_N) are pairwise distinct.
- (a_i, b_i) and (a_{i+1}, b_{i+1}) are adjacent in one of the eight directions. In other words, \max(\vert a_i - a_{i+1} \vert, \vert b_i - b_{i+1} \vert) = 1.
- The letter written on (a_i, b_i) coincides with the i-th character of S.
Constraints
- 1 \leq H, W \leq 10
- G_{i, j} is a lowercase English letter.
- 1 \leq N \leq 5
- S is a length-N string consisting of lowercase English letters.
Input
The input is given from Standard Input in the following format:
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
Output
Print Yes if there is a conforming sequence of cells; print No otherwise.
Sample Input 1
3 3 ekz sza znz 5 snake
Sample Output 1
Yes
The sequence of cells (2, 1), (3, 2), (2, 3), (1, 2), (1, 1) satisfies all the conditions in the problem statement, so the answer is Yes.
Sample Input 2
2 5 qwert asdfg 4 awrg
Sample Output 2
No
Sample Input 3
3 3 abc zbc zzc 5 abcba
Sample Output 3
No