AT_abc308_d [ABC308D] Snuke Maze

题目描述

有一个 $H$ 行 $W$ 列的网格。以下将从上到下第 $i$ 行、从左到右第 $j$ 列的格子记作 $(i, j)$。网格的每个格子上都写有一个小写英文字母，$(i, j)$ 上写的字母等于给定字符串 $S_i$ 的第 $j$ 个字符。

すぬけ君想要通过不断移动到边上相邻的格子，从 $(1, 1)$ 走到 $(H, W)$。他希望所经过的格子（包括起点 $(1, 1)$ 和终点 $(H, W)$）上写的字母，按照经过的顺序依次为 s $\rightarrow$ n $\rightarrow$ u $\rightarrow$ k $\rightarrow$ e $\rightarrow$ s $\rightarrow$ n $\rightarrow \dots$，即不断循环 snuke 这五个字母。请判断是否存在这样的一条路径。

这里，两个格子 $(i_1, j_1)$ 和 $(i_2, j_2)$ 当且仅当 $|i_1 - i_2| + |j_1 - j_2| = 1$ 时，称为“边上相邻”。

更严格地说，请判断是否存在一个格子序列 $((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 < k)$，$(i_t, j_t)$ 和 $(i_{t+1}, j_{t+1})$ 边上相邻
• 对所有 $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。

输入输出样例 #1

输入 #1

2 3
sns
euk

输出 #1

Yes

输入输出样例 #2

输入 #2

2 2
ab
cd

输出 #2

No

输入输出样例 #3

输入 #3

5 7
skunsek
nukesnu
ukeseku
nsnnesn
uekukku

输出 #3

Yes

说明/提示

限制

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

样例解释 1

路径 $(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (2, 3)$，经过的格子上的字母依次为 s $\rightarrow$ n $\rightarrow$ u $\rightarrow$ k，满足条件。

由 ChatGPT 4.1 翻译