分数: 400 点
问题陈述
我们有一个网格 H 水平行和 W 垂直列。 我们表示为 (i,j) 的单元格 i从顶部开始的第行和 j左起第 列。 网格中的每个单元格上都写有一个小写英文字母。 信上写着 (i,j) 等于 j- 给定字符串的第一个字符 S_i.
Snuke 将重复移动到共享一侧的相邻单元格 (1,1) to (H,W)。
判断是否存在路径
其中写在访问过的单元格上的字母(包括首字母 (1,1) 和最终 (H,W))是
s \rightarrow n \rightarrow u \rightarrow k
\rightarrow e \rightarrow s \rightarrow n \rightarrow \dots,按访问顺序。
这里,一个细胞 (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);
- (i_{t+1},j_{t+1}) 是以下单元格的相邻单元格 (i_t,j_t) 分享一边,为所有人 t\ (1 \leq t < k);和
- 这封信写在 (i_t,j_t) 与 (((t-1) \bmod 5) + 1)- 第一个字符
snuke,对于所有 t\ (1 \leq t \leq k).
约束
- 2\leq H,W \leq 500
- H 和 W 是整数。
- S_i 是一个长度为的字符串 W 由小写英文字母组成。
输入
输入由标准输入按以下格式给出:
H W S_1 S_2 \vdots S_H
输出
打印 Yes 如果存在满足问题陈述中的条件的路径;打印 No 否则。
示例输入 1
2 3 sns euk
示例输出 1
Yes
路径 (1,1) \rightarrow (1,2) \rightarrow (2,2) \rightarrow (2,3) 满足条件
因为他们有
上面写着 s \rightarrow n \rightarrow u \rightarrow k ,按照访问的顺序。
示例输入 2
2 2 ab cd
示例输出 2
No
示例输入 3
5 7 skunsek nukesnu ukeseku nsnnesn uekukku
示例输出 3
Yes