라이트 업
시간 제한2초메모리 제한256 MB
N×N 라이트 업 판의 흰 칸에 전구를 놓아 모든 흰 칸이 빛나게 하고 숫자가 적힌 검은 칸마다 인접 전구 개수를 맞추며, 사전순으로 가장 작은 배치를 찾는다.
문제
라이트 업은 격자판에 백열 전구를 놓는 퍼즐이다. 격자판의 각 칸은 검은색 정사각형이거나 흰색 정사각형이다. 목표는 흰색 정사각형 몇 곳에 백열 전구를 놓아 모든 흰색 정사각형에 불이 들어오게 하는 것이다.
어떤 흰색 정사각형과 같은 가로줄 또는 같은 세로줄에 백열 전구가 있고 그 사이에 검은색 정사각형이 하나도 없으면, 그 흰색 정사각형에 불이 들어온다. 전구를 놓은 칸도 불이 들어온 칸이다. 전구는 흰색 정사각형에만 놓을 수 있다.
그림 1
그림 1의 격자판에서 (3, 3)에 전구를 놓으면 그림 2와 같은 상황이 된다.
그림 2
이미 불이 들어온 흰색 정사각형에 전구를 놓으면 전구가 과열되므로 그런 배치는 할 수 없다. 즉 그림 3처럼 (2, 3)과 (3, 3)에 전구를 함께 놓는 것은 불가능하다.
그림 3
숫자가 적힌 검은색 정사각형도 있다. 이 숫자는 그 정사각형과 변을 맞댄 칸 가운데 전구가 놓여야 하는 칸의 개수다. 그림 4의 판을 보자.
그림 4
그림 5는 그림 4의 판에서 규칙을 모두 만족하는 배치 하나다.
그림 5
격자판이 주어지면 퍼즐을 푸는 배치를 찾아라.
입력
첫 줄에 테스트 케이스의 수 가 주어진다. ()
각 테스트 케이스의 첫 줄에 격자판의 크기 이 주어진다. ()
이어지는 개의 줄에 각각 개의 정수가 공백으로 구분되어 주어진다. 번째 줄의 번째 정수는 칸의 정보 다. 가 이면 흰색 정사각형, 이면 숫자가 없는 검은색 정사각형, 이상 이하이면 그 숫자가 적힌 검은색 정사각형이다.
출력
각 테스트 케이스마다 개의 줄에 걸쳐 또는 인 정수 개를 공백으로 구분해 출력한다. 전구를 놓은 칸은 , 놓지 않은 칸은 이다. 테스트 케이스의 답은 입력에 주어진 순서대로 이어서 출력한다.
답이 항상 존재하는 입력만 주어진다. 규칙을 만족하는 배치가 여럿이면 그중 사전순으로 가장 작은 배치 하나만 출력한다. 배치를 첫 줄부터 마지막 줄까지, 각 줄에서는 왼쪽부터 오른쪽으로 읽어 길이 인 과 의 수열로 보고, 이 수열이 사전순으로 가장 작은 배치가 답이다. 다시 말해 이 순서로 칸을 하나씩 볼 때, 그 칸에 을 놓고도 나머지 칸을 채워 퍼즐을 풀 수 있으면 그 칸은 이다.