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