← 返回题目列表

AtCoder · abc308_d

G. 蛇核迷宫

中文机器翻译题面 查看原题

分数: 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