크로스워드 도면
시간 제한1초메모리 제한128 MB
0과 1로 된 격자를 확대한 ASCII 십자말풀이 그림으로 바꾸고, 흰 칸에 번호를 붙이며 테두리와 이어진 검은 칸을 지운다.
문제
크로스워드는 0과 1로 이루어진 행렬로 저장할 수 있다. 0은 흰 칸, 1은 검은 칸을 뜻한다. 일부 흰 칸에는 번호가 매겨지며, 각 번호는 가로 또는 세로로 채워 넣을 단어의 설명을 가리킨다.
흰 칸에 번호가 매겨지는 조건은 다음 두 가지 중 하나이다.
- (a) 바로 아래 칸이 흰 칸이면서 바로 위에는 흰 칸이 없다.
- (b) 바로 왼쪽에 흰 칸이 없으면서 바로 오른쪽 칸이 흰 칸이다.
번호는 위쪽 행부터 아래쪽 행으로, 각 행에서는 왼쪽에서 오른쪽 순서로 1부터 매긴다.
행렬로부터 도면을 그린다. 각 칸은 높이 4문자, 너비 6문자의 상자가 되며, 이웃한 상자는 맞닿는 경계 행·열을 공유한다(따라서 도면 전체 크기는 행 열이다). 검은 칸은 다음과 같이 그린다.
++++++
++++++
++++++
++++++
흰 칸은 다음과 같이 그린다(왼쪽은 번호가 있는 칸, 오른쪽은 번호가 없는 칸).
++++++ ++++++
+nnn + + +
+ + + +
++++++ ++++++
여기서 nnn은 칸의 번호이며 앞을 0으로 채운 세 자리 숫자로 적는다.
상자 안의 나머지 문자는 모두 공백이다. 격자의 가장자리에 닿는 검은 칸은, 그리고 다른 검은 칸을 통해 그 칸과 이어진 모든 검은 칸은 도면에서 지워져 공백으로 그린다. 흰 칸으로 완전히 둘러싸인 검은 칸은 그대로 검은 칸으로 남는다. 공백은 필요한 곳에만 쓰고, 각 줄 끝에 불필요한 공백을 남기지 않는다.
입력
입력은 여러 블록으로 이루어지며, 각 블록은 하나의 크로스워드를 나타낸다. 각 블록의 첫 줄에는 공백 하나로 구분된 두 정수 와 가 주어진다. 이어지는 개의 줄에는 각각 공백으로 구분된 개의 정수(0 또는 1)가 주어진다. 입력은 첫 줄이 0 0인 블록으로 끝나며, 이 종료 블록에는 격자가 없고 그리지 않는다.
출력
종료 블록을 제외한 각 블록에 대해 대응하는 도면을 출력한다. 각 줄 끝에는 공백을 남기지 않는다. 연속한 두 도면 사이는 빈 줄 두 개로 구분한다.