测评会员优惠活动进行中 · 开通 VIP,有效期内测评不限次 VIP 优惠中 · 测评不限次 立即查看

A6272. Welcome24ever 和益智游戏

编程题 普及/提高-
知识点

题目描述

Welcome24ever 正在玩一款名为「Two Dots」的手机益智游戏。游戏的基础关卡是在一个 $n \times m$ 的棋盘上进行,如下图所示:


![](/uploads/acgo/image/90c71fdaf8465d3b_df0d1157dca0.jpg)


每个格子里有一个点,每个点都有一个颜色。我们用不同的大写英文字母表示不同的颜色。

这个游戏的关键是寻找由同色点组成的环。例如,上图中有四个蓝色点围成一个环。严格来说,我们把一串点 $d_1, d_2, \dots, d_k$ 称为一个环,当且仅当它满足以下条件:

1. 这 $k$ 个点互不相同:如果 $i \ne j$,那么 $d_i$ 和 $d_j$ 表示的格子不同;
2. $k$ 至少为 $4$;
3. 所有的点颜色相同;
4. 对于所有 $1 \le i \le k-1$,$d_i$ 和 $d_{i+1}$ 是相邻的,同时 $d_k$ 和 $d_1$ 也应当相邻。
如果两个格子有公共边,则称它们相邻(只能上下左右,不可以斜着)。

请你判断棋盘上是否存在这样一个同色环。

输入格式

第一行包含两个整数 $n$ 和 $m$($2 \le n, m \le 50$),表示棋盘的行数和列数。

接下来 $n$ 行,每行是一个长度为 $m$ 的字符串,表示这一行每个格子的颜色。
每个字符是一个大写英文字母。

输出格式

如果存在满足条件的环,则输出:

```text
Yes
```

否则输出:

```text
No
```

输入输出样例

输入 #1
3 4
AAAA
ABCA
AAAA
输出 #1
Yes
输入 #2
3 4
AAAA
ABCA
AADA
输出 #2
No
输入 #3
4 4
YYYR
BYBY
BBBY
BBBY
输出 #3
Yes
输入 #4
7 6
AAAAAB
ABBBAB
ABAAAB
ABABBB
ABAAAB
ABBBAB
AAAAAB
输出 #4
Yes
输入 #5
2 13
ABCDEFGHIJKLM
NOPQRSTUVWXYZ
输出 #5
No
上一题 去做题 下一题