Bai 1

 avatar
lalisadnn
plain_text
2 months ago
1.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

Leave a Comment