← 返回题单
题单练习 深度优先搜索
← 上一题 下一题 →

A6272 | Welcome24ever 和益智游戏

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

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





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

这个游戏的关键是寻找由同色点组成的环。例如，上图中有四个蓝色点围成一个环。严格来说，我们把一串点 $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$ 的字符串，表示这一行每个格子的颜色。
每个字符是一个大写英文字母。

输出格式

如果存在满足条件的环，则输出：

Yes


否则输出：

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
C++ 编辑器
输入
输出