Boccher Hide-and-Seek
View as PDFBand K consists of ~4~ members: HG, NI, RY, and IK. Apart from practicing and making music, the band occasionally organizes some recreational activities to bring the members closer together and increase the band's solidarity.
Today, they decided to play hide and seek, and this time they will play on the schoolyard. The schoolyard can be considered as a grid with size ~n \times m~, with rows numbered from ~1~ to ~n~, and columns numbered from ~1~ to ~m~. When viewed from above, the cell at row ~i~ and column ~j~ has color ~c_{i,j}~.
Due to her shy and timid personality, HG is chosen to be the one who hides. Understanding HG's personality, the other three members NI, RY, and IK guess that HG will curl up into a stone. This stone will have the shape of a ~2 \times 2~ square and will occupy ~4~ cells on the schoolyard.
Furthermore, this stone will have a very distinctive color. The stone will have ~3~ distinct colors, such that the color of ~2~ cells in the second column are the same. Specifically, if the stone occupies ~4~ cells ~(i, j)~, ~(i + 1, j)~, ~(i, j + 1)~, and ~(i + 1, j + 1)~, then:
~c_{i, j} \ne c_{i + 1, j}~,
~c_{i, j} \ne c_{i, j + 1}~,
~c_{i + 1, j} \ne c_{i + 1, j + 1}~,
~c_{i, j + 1} = c_{i + 1, j + 1}~.
Illustration for the fourth example. The highlighted square in the figure represents a valid stone of HG.
You are given the colors of the cells on the schoolyard. Determine whether HG is hiding on the schoolyard or not.
Input
The first line contains two integers ~n~ and ~m~ (~2 \le n, m \le 500~) – the size of the schoolyard.
The ~i~-th line of the next ~n~ lines contains a string of length ~m~ consisting of uppercase English letters. The ~j~-th character represents the color ~c_{i, j}~.
Output
Print "YES" if there exists a ~2 \times 2~ square on the schoolyard that matches the description of HG's stone. Otherwise, print "NO".
Scoring
The score for this problem is ~500~ points.
Sample Input 1
2 2
BP
YP
Sample Output 1
YES
Sample Input 2
3 3
VOI
IOI
TST
Sample Output 2
YES
Sample Input 3
5 5
QWERT
YUIOP
ASDFG
HJKLZ
XCVBN
Sample Output 3
NO
Sample Input 4
16 16
WWWWWWWWWWWWWWWW
WPPWWWWWWWWWWWWW
PWWPWWWPPWWWWWWW
WWWWBPPPPPPWWWWW
WWWWYPPPPPPPWWWW
WWWPPPPPPPPPPWWW
WWWPGGGPPGGGPWWW
WWWPPPGPPGPPPWWW
WWWPPGPPPPGPPWWW
WWWPGPPPPPPGPWWW
WWWPBPPPPPPBPWWW
WWPPPPPPPPPPPPWW
WWPPPPPPPPPPPPWW
WPPPPWPPPPWPPPPW
WPPPWWWPPWWWPPPW
WWWWWWWWWWWWWWWW
Sample Output 4
YES
Notes
In the first example, the schoolyard has size ~2 \times 2~. There is only one ~2 \times 2~ square on the schoolyard that matches the description of HG's stone.
The fourth example has an illustration in the problem statement.
Comments
Bocchi cục đá
ỏ
Bocchi the rock
Bochi the rock