Snuke 迷宫

题目描述

我们有一个 $H$ 行 $W$ 列的网格。用 $(i,j)$ 表示从上数第 $i$ 行、从左数第 $j$ 列的格子。

网格的每个格子上都写有一个小写英文字母。写在 $(i,j)$ 上的字母等于给定字符串 $S_i$ 的第 $j$ 个字符。

Snuke 将反复移动到共享一条边的相邻格子,从 $(1,1)$ 走到 $(H,W)$。

判断是否存在一条路径,使得访问过的格子(包括起点 $(1,1)$ 和终点 $(H,W)$)上写着的字母按访问顺序依次为 $s \rightarrow n \rightarrow u \rightarrow k \rightarrow e \rightarrow s \rightarrow n \rightarrow \dots$。

这里,当且仅当 $|i_1-i_2|+|j_1-j_2| = 1$ 时,称格子 $(i_1,j_1)$ 是 $(i_2,j_2)$ 的共享一条边的相邻格子。

形式化地说,判断是否存在满足以下条件的格子序列 $((i_1,j_1),(i_2,j_2),\dots,(i_k,j_k))$:

• $(i_1,j_1) = (1,1),(i_k,j_k) = (H,W)$;
• 对所有 $t\ (1 \leq t \lt k)$,$(i_{t+1},j_{t+1})$ 是 $(i_t,j_t)$ 的共享一条边的相邻格子;
• 对所有 $t\ (1 \leq t \leq k)$,写在 $(i_t,j_t)$ 上的字母与 snuke 的第 $(((t-1) \bmod 5) + 1)$ 个字符一致。

输入格式

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

$H$ $W$
$S_1$
$S_2$
$\vdots$
$S_H$

输出格式

如果存在满足题目描述中条件的路径,输出 Yes;否则输出 No。

样例

2 3
sns
euk

Yes

路径 $(1,1) \rightarrow (1,2) \rightarrow (2,2) \rightarrow (2,3)$ 满足条件,因为按访问顺序它们上面写着 $s \rightarrow n \rightarrow u \rightarrow k$。

2 2
ab
cd

No

5 7
skunsek
nukesnu
ukeseku
nsnnesn
uekukku

Yes

数据范围

• $2 \le H,W \le 500$
• $H$ 和 $W$ 是整数
• $S_i$ 是由小写英文字母组成的长度为 $W$ 的字符串