问题3634--Fox And Two Dots

3634: Fox And Two Dots

时间限制: 2 Sec  内存限制: 512 MB
提交: 0  解决: 0
[提交] [状态] [讨论版] [命题人:]

题目描述

Fox Ciel is playing a mobile puzzle game called "Two Dots". The basic levels are played on a board of size n×m cells. Fox Ciel正在玩一个被称作"Two Dots"的手机益智类游戏。基本等级是在一个n*m单元的板子上玩。 图如下(外网):[IMG]http://codeforces.com/predownloaded/40/54/4054f56d341c153a25dbc44b4a1e613d802d0149.png[/IMG] Each cell contains a dot that has some color. We will use different uppercase Latin characters to express different colors. 每一个单元里都有一个点,点上有颜色。我们将用不同的字母表示颜色。 The key of this game is to find a cycle that contain dots of same color. Consider 4 blue dots on the picture forming a circle as an example. Formally, we call a sequence of dots d1,d2,...,dk a cycle if and only if it meets the following condition: 本游戏的关键是要串联相同颜色的点串联起来,形成一个圈。例如,一组d1,d2,...,dk围成一个圈要符合以下几点: 1.These k dots are different: if i≠j then di is different from dj. 这k点是不同的:如果i≠j那么 di≠dj。 2.k is at least 4. k至少是4。 3.All dots belong to the same color. 所有点的颜色相同 4.For all 1≤i≤k-1: di and di+1 are adjacent. Also, dk and d1 should also be adjacent. Cells x and y are called adjacent if they share an edge. 对于所有的 1≤i≤k-1:di和di+1是相邻的,且dk和d1也是相邻的。如果单元x,y公用一条边那么我们称单元x和y是相邻的。 Determine if there exists a cycle on the field. 你要做的是:确定图中是否有一个圈。

输入

The first line contains two integers n and m (2≤n,m≤50): the number of rows and columns of the board. 第一行输入两个整数 n和m:板中行数和列数。 Then n lines follow, each line contains a string consisting of m characters, expressing colors of dots in each line. Each character is an uppercase Latin letter. 接下来n行,每行m个字符,输入圆点的颜色(用字母表示)。

输出

Output "Yes" if there exists a cycle, and "No" otherwise. 如果有圈,那么输出"Yes",否则输出"No"

样例输入

3 4
AAAA
ABCA
AAAA


3 4
AAAA
ABCA
AADA


4 4
YYYR
BYBY
BBBY
BBBY


7 6
AAAAAB
ABBBAB
ABAAAB
ABABBB
ABAAAB
ABBBAB
AAAAAB


2 13
ABCDEFGHIJKLM
NOPQRSTUVWXYZ

样例输出

Yes


No


Yes


Yes


No

来源/分类


[提交] [状态]