A5404. Snuke Maze
编程题
普及/提高-
知识点
题目描述
有一个 $H$ 行 $W$ 列的网格。以下将从上到下第 $i$ 行、从左到右第 $j$ 列的格子记作 $(i, j)$。网格的每个格子上都写有一个小写英文字母，$(i, j)$ 上写的字母等于给定字符串 $S_i$ 的第 $j$ 个字符。
すぬけ君想要通过不断移动到边上相邻的格子，从 $(1, 1)$ 走到 $(H, W)$。他希望所经过的格子（包括起点 $(1, 1)$ 和终点 $(H, W)$）上写的字母，按照经过的顺序依次为
这里，两个格子 $(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)$
- 对所有 $t\ (1 \leq t < k)$，$(i_t, j_t)$ 和 $(i_{t+1}, j_{t+1})$ 边上相邻
- 对所有 $t\ (1 \leq t \leq k)$，$(i_t, j_t)$ 上写的字母等于
すぬけ君想要通过不断移动到边上相邻的格子，从 $(1, 1)$ 走到 $(H, W)$。他希望所经过的格子（包括起点 $(1, 1)$ 和终点 $(H, W)$）上写的字母，按照经过的顺序依次为
s $\rightarrow$ n $\rightarrow$ u $\rightarrow$ k $\rightarrow$ e $\rightarrow$ s $\rightarrow$ n $\rightarrow \dots$，即不断循环 snuke 这五个字母。请判断是否存在这样的一条路径。这里，两个格子 $(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)$
- 对所有 $t\ (1 \leq t < k)$，$(i_t, j_t)$ 和 $(i_{t+1}, j_{t+1})$ 边上相邻
- 对所有 $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$
> $H$ $W$
> $S_1$
> $S_2$
> $\vdots$
> $S_H$
输出格式
如果存在满足题意的路径，输出
Yes；否则输出 No。输入输出样例
输入 #1
2 3 sns euk
输出 #1
No
输入 #2
2 2 ab cd
输出 #2
Yes
说明/提示
## 限制
- $2 \leq H, W \leq 500$
- $H, W$ 为整数
- $S_i$ 是由小写英文字母组成的长度为 $W$ 的字符串
## 样例解释 1
路径 $(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (2, 3)$，经过的格子上的字母依次为
- $2 \leq H, W \leq 500$
- $H, W$ 为整数
- $S_i$ 是由小写英文字母组成的长度为 $W$ 的字符串
## 样例解释 1
路径 $(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (2, 3)$，经过的格子上的字母依次为
s $\rightarrow$ n $\rightarrow$ u $\rightarrow$ k，满足条件。