#ABC308D. Snuke 的迷宫

Snuke 的迷宫

题目描述

\hspace{15pt}给定一个 n×mn\times m 的小写字母网格。从左上角 (1,1)(1,1) 出发,每步可移动到上下左右相邻的一个格子,不能越界。

\hspace{15pt}经过的格子包括起点与终点,字母必须依次为 $\texttt{`s'}\to\texttt{`n'}\to\texttt{`u'}\to\texttt{`k'}\to\texttt{`e'}\to\texttt{`s'}\to\dots$,即循环重复字符串 "snuke"\texttt{"snuke"}。

\hspace{15pt}判断是否存在满足条件、到达右下角 (n,m)(n,m) 的路径。终点可以位于循环中的任意位置,不要求恰好经过完整的五个字母。

输入格式

\hspace{15pt}第一行输入两个整数 n,m(2≦n,m≦500)n,m\left(2\leqq n,m\leqq500\right)。

\hspace{15pt}此后 nn 行,每行输入一个长度为 mm 的小写英文字母字符串,代表对应行的字母。

输出格式

\hspace{15pt}存在合法路径时输出 "Yes"\texttt{"Yes"},否则输出 "No"\texttt{"No"}。

测试样例

2 3
sns
euk
Yes

样例 1 解释

\hspace{15pt}路径为 (1,1)→(1,2)→(2,2)→(2,3)(1,1)\to(1,2)\to(2,2)\to(2,3),经过的字母依次为 $\texttt{`s'},\texttt{`n'},\texttt{`u'},\texttt{`k'}$,因此输出 "Yes"\texttt{"Yes"}。

2 2
ab
cd
No
5 7
skunsek
nukesnu
ukeseku
nsnnesn
uekukku
Yes