Snuke Maze

题目描述

我们有一个有 $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 < 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

2 2
ab
cd

No

5 7
skunsek
nukesnu
ukeseku
nsnnesn
uekukku

Yes

提示

$2\leq H,W \leq 500$ $H$ 和 $W$ 是整数。 $S_i$ 是长度为 $W$ 的由小写英文字母组成的字符串。路径 $(1,1) \rightarrow (1,2) \rightarrow (2,2) \rightarrow (2,3)$ 满足条件， 因为这些格子按访问顺序分别写有 $s$ $\rightarrow$ $n$ $\rightarrow$ $u$ $\rightarrow$ $k$。

标签: AtCoder|abc308D

来源

AtCoder|abc308D