Jigglypuff
시간 제한1초메모리 제한512 MB
문자 격자가 주어질 때, 왼쪽 위에서 오른쪽 아래로 가는 서로 다른 단조 경로 세 개가 같은 문자열을 만들 수 있는지 판정한다.
문제
Your ACM team has gathered in a picturesque city of Petrozavodsk for a team-building camp. You’ve heard that just outside of the city there is a Jigglypuff field that might help you make stronger bonds with your teammates, so you’re definitely giving it a try.
The field is a rectangle partitioned into n · m squares grouped into n rows and m columns. Each square contains a single Jigglypuff, which produces a note when a team member steps on its cell. Each note can be described by a single lowercase English character.
You and your two teammates will stand in the top-left corner of the field. Each of you will then go to the bottom-right corner, moving only right and down. Each of you has to pick a different route through the field.
Jigglypuff have psychic abilities. Therefore, if each of you hears exactly the same sequence of notes when passing through the field, your brains will perfectly synchronize and the team-building exercise will be complete. Is it possible to do so?
입력
The first line contains two integers n, m (2 ≤ n, m ≤ 3000) — the height and the width of the field. The following n lines describe the field. Each of these lines contains a single string of length m consisting of lowercase English characters. The first character in the first line is the top-left corner of the field.
출력
Output YES if it’s possible to hear the same sequence of notes on at least three different routes through the grid, or NO otherwise. Each character can be printed in any case (either uppercase or lowercase).
힌트
The following picture shows the first example test and three paths generating the same sequence of notes — petrozavodsk:
