← 返回题目列表

Codeforces · 510/B

B. 狐狸和两个点

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

Fox Ciel 正在玩一款名为“Two Dots”的手机益智游戏。基本关卡是在大小为 n × m 的棋盘上进行的,如下所示:

每个单元格都包含一个具有某种颜色的点。我们将使用不同的大写拉丁字符来表示不同的颜色。

这个游戏的关键是找到包含相同颜色点的循环。以图片上的 4 个蓝点形成一个圆圈为例。形式上,当且仅当满足以下条件时,我们将点序列 d1, d2, ..., dk 称为循环:

1. 这 k 个点不同:如果 i ≠ j,则 di 与 dj 不同。
2. k 至少为 4。
3. 所有点都属于同一颜色。
4. 对于所有 1 ≤ i ≤ k - 1:di 和 di + 1 是相邻的。此外,dk 和 d1 也应该相邻。如果单元格 x 和 y 共享一条边,则它们被称为相邻单元格。

确定现场是否存在循环。

输入

第一行包含两个整数n和m(2≤n,m≤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

注意

在第一个样本测试中,所有“A”形成一个循环。

在第二个示例中没有这样的循环。

第三个示例如上图所示(“Y”= 黄色,“B”= 蓝色,“R”= 红色)。