问题3634--Fox And Two Dots3634: 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
来源/分类
[提交] [状态]