Boccher Hide-and-Seek

View as PDF

Submit solution


Points: 0.20 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Band 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}~.

image

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

Please read the guidelines before commenting.



  • -1
    toidaidot2  commented on July 13, 2023, 12:53 p.m.

    Bocchi the rock


  • 17
    makisezef  commented on June 1, 2023, 12:24 p.m.

    Bochi the rock