샤카샤카
시간 제한1초메모리 제한1024 MB
3N x 3M 크기의 아스키 아트를 3x3 단위로 잘라 각 칸의 블록을 복원한 뒤, 주어진 해답이 샤카샤카의 정답 조건을 만족하는지 판별한다.
문제
샤카샤카는 직사각형 보드 위에서 즐기는 퍼즐 게임이다. 보드는 \(N\)행 \(M\)열의 격자로 구분되어 있으며, 각 칸에 블록을 하나 놓을 수 있다. 퍼즐을 해결하려면 게임을 시작하기 전 주어지는 보드의 블록들을 적절히 교체하여 정답 조건을 만족시켜야 한다.
샤카샤카의 블록은 다음과 같은 여섯 종류이다. 앞의 2개는 정사각형 블록, 뒤의 4개는 삼각형 블록이라고 부르자.
또한, 검은색 정사각형 블록 위에는 다음과 같이 0 이상 4 이하의 숫자가 적혀있을 수 있다.
초기 보드의 각 칸에는 정사각형 블록이 놓여있다. 플레이어는 흰색 정사각형 블록을 원하는 삼각형 블록으로 바꿀 수 있으며, 정답 조건을 만족시키려면 다음 내용을 모두 만족해야 한다.
- 연속한 모든 흰색 영역은 직사각형이다. 단, 그 변이 가로축 또는 세로축과 평행할 필요는 없다.
- 숫자 \(k\)가 적힌 정사각형 블록의 상하좌우 4칸에는 삼각형 블록이 정확히 \(k\)개 있어야 한다.
샤카샤카의 일반적인 해법을 구하는 것은 NP-Complete 문제로 아주 어렵다는 것이 잘 알려져 있다. 퍼즐을 푸는 대신 주어진 샤카샤카 해답이 정답 조건을 만족하는지 판별하는 프로그램을 작성하여라.
입력
입력의 첫 번째 줄에는 보드의 크기 \(N\), \(M\)이 주어진다.
다음 3\(N\)개의 줄에는 샤카샤카의 해답이 다음과 같은 조건으로 주어진다.
본문의 6가지 블록은 다음과 같은 3 × 3 아스키 아트로 주어진다.
또한 검은색 정사각형 블록 안에 숫자가 있는 경우, 다음과 같이 해당 블록의 가운데에 숫자가 위치한다.
샤카샤카의 해답은 3\(N\) × 3\(M\)개의 문자로 주어지며, 위와 같이 3 × 3 단위로 끊어서 어떤 블록이 어느 위치에 있는지 해석할 수 있다.
출력
주어진 해답이 정답 조건을 만족하면 YES, 아니면 NO를 출력한다.
제한
- 1 ≤ \(N\), \(M\) ≤ 10