모자이크 논리 퍼즐
시간 제한2초메모리 제한512 MB
3x3 이웃 중 검은 칸의 개수를 알려주는 단서가 격자 바깥까지 주어질 때, 각 칸을 검게 칠하거나 불가능을 판정한다.
문제
최근 여행지의 키오스크에서 각종 논리 퍼즐이 가득한 잡지를 샀다. 얼마 동안 퍼즐을 풀다 보니 조금 지루해졌다. 그래도 잡지의 모든 퍼즐을 다 풀고 싶은 마음에, 몇몇 퍼즐을 알고리즘으로 해결할 방법을 고민하기 시작한다.
지금 풀려는 퍼즐의 이름은 모자이크(Mosaic)이고, 고전 게임 지뢰찾기와 꽤 비슷하다:
그림 L.1: 첫 번째 예시의 그림
처음에 모두 하얀색인 2차원 격자가 주어지고, 이 중 일부 칸을 검은색으로 칠해야 한다. 격자 바깥으로 사방 한 칸씩 확장된 힌트 숫자 격자도 주어진다. 어떤 칸의 숫자는 그 칸을 중심으로 한 3 × 3 영역 안에서 검은색으로 칠해야 하는 칸의 수를 나타낸다. 원래 격자 밖의 칸은 칠할 수 없다.
입력
입력은 다음과 같다.
- 한 줄에 두 정수 h, w (1 ≤ h, w ≤ 100)가 주어지며, 각각 퍼즐의 높이와 너비이다.
- h + 2개의 줄이 주어지며, 각 줄에 w + 2개의 정수 c1, . . . , cw+2 (0 ≤ ci ≤ 9)가 주어진다. 이는 힌트 숫자이다.
출력
주어진 힌트 숫자가 서로 모순되면 impossible을 출력한다. 그렇지 않으면 퍼즐의 해를 나타내는 h개의 줄을 출력한다. 각 줄은 w개의 문자로 이루어지며, 검은색 칸에는 X, 하얀색 칸에는 .을 출력한다. 해가 여러 개라면 그중 아무거나 출력해도 된다.