#223. 狐仙的魔法连线

狐仙的魔法连线

题目描述

狐仙小月最近迷上了一款名为「魔法连线」的益智游戏。这款游戏在一个 n×mn \times m 的魔法棋盘上进行,每个格子中都有一个魔法符文,每个符文都有不同的颜色(用大写的拉丁字母表示)。

小月的目标是找到一个由相同颜色符文组成的魔法回路。例如,下图中的蓝色符文就构成了一个魔法回路: image

魔法回路的定义

如果一组符文满足以下条件,则它们可以构成一个魔法回路:

  1. 回路中的所有符文颜色相同;
  2. 回路中符文的数量至少为 44
  3. 回路中没有重复符文:即符文 d1,d2,,dkd_1, d_2, \dots, d_k 是不同的;
  4. 符文 d1,d2,,dkd_1, d_2, \dots, d_k 按顺序两两相邻,且最后一个符文 dkd_k 与第一个符文 d1d_1 也相邻。

其中,两个符文相邻的条件是:它们共享一条边。

你的任务是判断,这个魔法棋盘上是否存在一个符合条件的魔法回路。

输入格式

第一行:两个整数 nnmm (2n,m50)(2 \leq n, m \leq 50),表示棋盘的行数和列数。

接下来的 nn 行,每行包含一个长度为 mm 的字符串,表示棋盘上符文的颜色。

输出格式

如果存在魔法回路,输出 "Yes";否则输出 "No"

样例

3 4
AAAA
ABCA
AAAA
Yes
3 4
AAAA
ABCA
AADA
No
4 4
YYYR
BYBY
BBBY
BBBY
Yes
7 6
AAAAAB
ABBBAB
ABAAAB
ABABBB
ABAAAB
ABBBAB
AAAAAB
Yes
2 13
ABCDEFGHIJKLM
NOPQRSTUVWXYZ
No

解释

对于第一个样例,所有颜色为AA的符文可以构成一个魔法回路。

对于第二个样例,棋盘上没有符合条件的魔法回路。