G - Find the Snaky

Contest Duration: 2023-12-02(Sat) 04:00 - 2023-12-02(Sat) 09:00 (local time) (300 minutes) Back to Home

G - Find the Snaky Editorial

Time Limit: 2 sec / Memory Limit: 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 を出力せよ。

入力例 1Copy

Copy

3 3
ekz
sza
znz
5
snake

出力例 1Copy

Copy

Yes

マスの列 $(2, 1), (3, 2), (2, 3), (1, 2), (1, 1)$ は問題文の条件を全て満たします。よって答えは Yes です。

入力例 2Copy

Copy

2 5
qwert
asdfg
4
awrg

出力例 2Copy

Copy

No

入力例 3Copy

Copy

3 3
abc
zbc
zzc
5
abcba

出力例 3Copy

Copy

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 1Copy

Copy

3 3
ekz
sza
znz
5
snake

Sample Output 1Copy

Copy

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 2Copy

Copy

2 5
qwert
asdfg
4
awrg

Sample Output 2Copy

Copy

No

Sample Input 3Copy

Copy

3 3
abc
zbc
zzc
5
abcba

Sample Output 3Copy

Copy

No