연날이

시간 제한1초메모리 제한512 MB

요약

블록이 떨어지는 격자에서 가로로 인접한 두 칸을 한 번 맞바꿔 연쇄 반응으로 모든 블록을 없앨 수 있는지 판정한다.

난이도: 보통10점 중 7점
유형: 시뮬레이션, 구현, 완전 탐색, BFS
정답자: 아직 제출이 없습니다

문제

연날이에 온 토끼가 어떤 가게의 게임 상품이 당근 케이크라는 것을 발견했다. 이 게임의 규칙은 다음과 같다.

세로 $h$ 칸, 가로 $w$ 칸의 격자 모양 필드가 있고, 각 칸에는 블록이 많아야 1개 놓인다. 각 블록에는 알파벳 대문자('A' - 'Z') 중 하나로 나타내는 색이 칠해져 있다. 같은 색 블록이 세로 또는 가로로 일직선상에 $n$ 개 이상 연속해서 늘어서면 그 블록들은 소멸한다.

참가자는 가로로 인접한 두 칸을 골라 그 상태를 서로 바꾸는 조작을 할 수 있다. 블록의 교환, 소멸, 낙하로 인해 블록이 있는 칸의 바로 아래 칸에 블록이 없어지면, 이 블록은 낙하한다. 이때 다시 같은 색 블록이 $n$ 개 이상 늘어서면 소멸한다. 다만 블록의 소멸은 낙하하는 블록이 존재하는 동안에는 일어나지 않고, 모든 블록의 낙하가 끝난 시점에 동시에 일어난다.

1번의 조작으로 필드 위의 모든 블록을 소멸시키면 이 게임은 성공이 되고 상품인 케이크를 얻을 수 있다. 토끼는 1회분 참가비로 확실하게 케이크를 손에 넣고 싶어 하며, 그럴 수 없다면 참가하고 싶어 하지 않는다. 게임 시작 시점의 필드 상태로부터 토끼가 이 게임에 참가해야 하는지 답하라.

입력

입력의 첫째 줄에는 $h$ , $w$ , $n$ 이 공백으로 구분되어 주어진다.

$2 \le h, w, n \le 30$

이어지는 $h$ 개 줄에는 필드의 상태가 위에서부터 순서대로 주어진다. 알파벳 대문자는 블록을, '.'은 빈칸을 나타낸다. 주어지는 필드 상태에는 세로 또는 가로로 $n$ 개 이상 연속하는 같은 색 블록이 없고, 낙하하는 상태에 있는 블록도 없다. 블록이 1개 이상 존재한다.

출력

토끼가 이 게임에 참가해야 한다면 "YES"를, 그렇지 않다면 "NO"를 한 줄에 출력하라.

예제2

예제 1
입력
```
4 6 3
......
...Y..
...Y..
RRYRYY
```
예상 출력
```
YES
```
예제 2
입력
```
4 6 3
......
...Y..
...Y..
RRYRY.
```
예상 출력
```
NO
```