shinwa_campus

 avatar
SSkyFire
java
2 months ago
2.8 kB
1
Indexable
Never
In the previous problem, "Shinwa Makes Buildings For Employees", you helped Shinwa company to fix the positions of the buildings to be made for its employees. However, the main campus of Shinwa company already consists of office buildings which were build many years ago. Shinwa company wants to re-innovate the buildings and color them.
Let the office campus can be denoted as n*m grid where each cell denotes a office building. We use different uppercase Latin characters to express different colors. However, the manager who is in charge of coloring the buildings is a very interesting person. He wants to remove the cycles made by the same colored buildings. Formally we call a sequence of buildings b1, b2, .... , b_k a cycle if and only if t meets the following condition:


 1. These k buildings are different: if i ≠ j then bi is different from bj.
 2. k is at least 4.
 3. All buildings belong to the same color.
 4. For all 1 ≤ i ≤ k-1: bi and bi+1 are adjacent. Also, bk and b1 should also be adjacent. Buildings x and y are called adjacent if they share an edge.
 
 Determine if there exists a cycle in Shinwa office campus.
 
Input
First line contains the number of test case, t.
For each test case,
the first line contains two integers n and m (2≤n,m≤50): the number of rows and columns of the board.
Then n lines follow, each line contains a string consisting of m characters, expressing colors of buildings in each line. Each character is an upper-case Latin letter.

Output
Output "Yes" if there exists a cycle in campus, and "No" otherwise.

Sample Input:
3
3 4
AAAA
ABCA
AAAA
3 4
AAAA
ABCA
AADA
7 6
AAAAAB
ABBBAB
ABAAAB
ABABBB
ABAAAB
ABBBAB
AAAAAB


Sample Output:
Case 1: Yes
Case 2: No
Case 3: Yes

13
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
2 2
AA
AA
2 2
AA
AB
3 3
AAA
ABA
AAA
3 3
AAA
ABA
ABA
10 10
EGFJGJKGEI
AKJHBGHIHF
JBABBCFGEJ
CJDJHJJKBD
KHJIKKGGEK
HHJHKHGEKF
EKFCAJGGDK
AFKBBFICAA
FEDFAGHEKA
CAAGIFHGGI
10 10
HIICQRHPUJ
BCDUKHMBFK
PFTUIDOBOE
QQPITLRKUP
ERMUJMOSMF
MRSICEILQB
ODIGFNCHFR
GHIOAFLHJH
FBLAQNGEIF
FDLEGDUTNG
2 50
DADCDBCCDAACDBCAACADBCBDBACCCCDADCBACADBCCBDBCCBCC
DADAADCABBBACCDDBABBBDCBACBCCCCDDADCDABADDDCABACDB
50 2
AA
CD
EE
FC
ED
AF
FC
AD
BA
AF
BF
DA
AC
FC
FA
BF
AD
BB
DC
AF
AA
AD
EE
ED
CD
FC
FB
BB
DD
EB
BE
CF
DE
AE
FD
AB
FB
AE
BE
FA
CF
FB
DE
ED
AD
FA
BB
BF
DA
EE

Case 1: Yes
Case 2: No
Case 3: Yes
Case 4: Yes
Case 5: No
Case 6: Yes
Case 7: No
Case 8: Yes
Case 9: No
Case 10: No
Case 11: No
Case 12: Yes
Case 13: No

Leave a Comment