开始: 2026-10-08 00:00:00

【集训06】模拟赛

结束: 2026-10-10 00:00:00
当前  2026-11-04 11:35:12  类型: IOI  状态: 已经结束 

P2. 字母迷宫(maze)
描述

有一个 H 行 W 列的方格网,第 i 行第 j 列的格子记作 (i,j)。每个格子里写着一个英文小写字母,第 i 行的字母依次给出(字符串 S_i 的第 j 个字符就是 (i,j) 中的字母)。

小Z要从 (1,1) 走到 (H,W),每一步只能移动到**上下左右相邻**的格子(不能走出网格)。他要求:**按访问顺序**,经过格子上的字母必须依次是

```

s → n → u → k → e → s → n → u → k → e → …

```

即循环出现单词 `snuke`。注意起点 (1,1) 和终点 (H,W) 也要满足这个顺序。

更严格地说,需要判断是否存在一个格子的序列 ((i_1,j_1),(i_2,j_2),\dots,(i_k,j_k)) 满足:

1. (i_1,j_1)=(1,1),(i_k,j_k)=(H,W);

2. 对所有 1\le t,(i_t,j_t) 与 (i_{t+1},j_{t+1}) 四邻相邻;

3. 对所有 1\le t\le k,(i_t,j_t) 上的字母等于 `snuke` 的第 ((t-1)\bmod 5)+1 个字符。

同一个格子**可以被多次经过**,只要字母顺序对得上。

问:是否存在满足条件的路径?


输入

第一行两个整数 H,W(2 \leq H,W \leq 500),表示网格的行数与列数。


接下来 H 行,第 i 行是一个长度为 W 的、仅含英文小写字母的字符串 S_i。


输出

若存在满足条件的路径,输出 `Yes`;否则输出 `No`。

样例

输入

2 3
sns
euk

输出

Yes

输入

5 7
skunsek
nukesnu
ukeseku
nsnnesn
uekukku

输出

Yes
提示

**样例 #1 解释**:路径 (1,1)\to(1,2)\to(2,2)\to(2,3),字母依次是 `s → n → u → k`,合法。

**样例 #2 解释**:起点 (1,1) 上是 `a`,不是 `s`,不可能开始,答案为 `No`。

**数据范围**:

- 2\le H,W\le 500;

- H,W 为整数;

- S_i 是长度 W 的英文小写字母串。


提交

题目参数
时间限制 1 秒
内存限制 128 MB
提交