시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1 1 1 100.000%

문제

희원이는 누리카베 퍼즐을 푸는 프로그램을 만드려고 한다.

누리카베 퍼즐은 직사각형 그리드 상에서 진행되며, 빈 칸과 숫자가 들어있는 칸이 있다. 이 게임을 풀기 위해서는 각 칸이 아래의 조건을 만족시키려면, 흰색(땅)이 될지 검정색(바다)가 될지 결정해야 한다. 섬은 흰 칸으로 최대한 연결된 구역을 말한다.

1. 검정색 칸은 모두 서로 연결되어 있어야 한다.

2. 숫자가 쓰여 있는 칸은 항상 섬의 일부이어야 한다.

3. 섬에 포함되어 있는 칸의 개수는 그 섬이 포함하고 있는 숫자 칸의 숫자와 같아야 한다.

4. 모든 섬에는 숫자 칸이 하나 있어야 한다.

5. 두 섬은 서로 연결되어 있으면 안된다.

6. 2×2 모양의 검정칸은 만들 수 없다.

칸은 대각선으로 연결될 수 없다. 항상 답이 유일한 경우만 입력으로 주어진다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 퍼즐의 크기 n과 m이 주어진다. (3 ≤ n, m ≤ 9)

다음 n개 줄에는 퍼즐의 초기 상태가 주어진다. 빈 칸은 '.'으로, 숫자 칸은 칸에 쓰여 있는 숫자로 주어진다. 칸에 쓰여 있는 숫자는 항상 한 자리이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

퍼즐을 푼 상태를 출력한다. 검정칸은 '#'으로 표시한다. 퍼즐과 퍼즐 사이에는 빈 줄을 하나씩 출력한다.

예제 입력 1

3 4
3...
....
.4..
5 5
2.5..
.....
.....
.....
..4.3
0 0

예제 출력 1

3..#
####
.4..

2#5..
.#.##
##.#.
.###.
..4#3
W3sicHJvYmxlbV9pZCI6IjYyNjgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIyMDRcdWI5YWNcdWNlNzRcdWJjYTAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDc2Y1x1YzZkMFx1Yzc3NFx1YjI5NCBcdWIyMDRcdWI5YWNcdWNlNzRcdWJjYTAgXHVkMzdjXHVjOTkwXHVjNzQ0IFx1ZDQ3OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHViOWNjXHViNGRjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMjA0XHViOWFjXHVjZTc0XHViY2EwIFx1ZDM3Y1x1Yzk5MFx1Yzc0MCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUgXHVhZGY4XHViOWFjXHViNGRjIFx1YzBjMVx1YzVkMFx1YzExYyBcdWM5YzRcdWQ1ODlcdWI0MThcdWJhNzAsIFx1YmU0OCBcdWNlNzhcdWFjZmMgXHVjMjJiXHVjNzkwXHVhYzAwIFx1YjRlNFx1YzViNFx1Yzc4OFx1YjI5NCBcdWNlNzhcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1ZDQ4MFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWNcdWIyOTQgXHVhYzAxIFx1Y2U3OFx1Yzc3NCBcdWM1NDRcdWI3OThcdWM3NTggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1YzJkY1x1ZDBhNFx1YjgyNFx1YmE3NCwgXHVkNzcwXHVjMGM5KFx1YjU0NSlcdWM3NzQgXHViNDIwXHVjOWMwIFx1YWM4MFx1YzgxNVx1YzBjOShcdWJjMTRcdWIyZTQpXHVhYzAwIFx1YjQyMFx1YzljMCBcdWFjYjBcdWM4MTVcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWMxMmNcdWM3NDAgXHVkNzcwIFx1Y2U3OFx1YzczY1x1Yjg1YyBcdWNkNWNcdWIzMDBcdWQ1NWMgXHVjNWYwXHVhY2IwXHViNDFjIFx1YWQ2Y1x1YzVlZFx1Yzc0NCBcdWI5ZDBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjEuIFx1YWM4MFx1YzgxNVx1YzBjOSBcdWNlNzhcdWM3NDAgXHViYWE4XHViNDUwIFx1YzExY1x1Yjg1YyBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+Mi4gXHVjMjJiXHVjNzkwXHVhYzAwIFx1YzRmMFx1YzVlYyBcdWM3ODhcdWIyOTQgXHVjZTc4XHVjNzQwIFx1ZDU2ZFx1YzBjMSBcdWMxMmNcdWM3NTggXHVjNzdjXHViZDgwXHVjNzc0XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+My4gXHVjMTJjXHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTQgXHVjZTc4XHVjNzU4IFx1YWMxY1x1YzIxOFx1YjI5NCBcdWFkZjggXHVjMTJjXHVjNzc0IFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyOTQgXHVjMjJiXHVjNzkwIFx1Y2U3OFx1Yzc1OCBcdWMyMmJcdWM3OTBcdWM2NDAgXHVhYzE5XHVjNTQ0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+NC4gXHViYWE4XHViNGUwIFx1YzEyY1x1YzVkMFx1YjI5NCBcdWMyMmJcdWM3OTAgXHVjZTc4XHVjNzc0IFx1ZDU1OFx1YjA5OCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD41LiBcdWI0NTAgXHVjMTJjXHVjNzQwIFx1YzExY1x1Yjg1YyBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHVjNzNjXHViYTc0IFx1YzU0OFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+Ni4gMiZ0aW1lczsyIFx1YmFhOFx1YzU5MVx1Yzc1OCBcdWFjODBcdWM4MTVcdWNlNzhcdWM3NDAgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2U3OFx1Yzc0MCBcdWIzMDBcdWFjMDFcdWMxMjBcdWM3M2NcdWI4NWMgXHVjNWYwXHVhY2IwXHViNDIwIFx1YzIxOCBcdWM1YzZcdWIyZTQuIFx1ZDU2ZFx1YzBjMSBcdWIyZjVcdWM3NzQgXHVjNzIwXHVjNzdjXHVkNTVjIFx1YWNiZFx1YzZiMFx1YjljYyBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL24xLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjI1N3B4OyB3aWR0aDoyNjlweFwiIFwvPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvbjIucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjU2cHg7IHdpZHRoOjI2NnB4XCIgXC8+PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMzdjXHVjOTkwXHVjNzU4IFx1ZDA2Y1x1YWUzMCBuXHVhY2ZjIG1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMyAmbGU7IG4sIG0gJmxlOyA5KTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgblx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMzdjXHVjOTkwXHVjNzU4IFx1Y2QwOFx1YWUzMCBcdWMwYzFcdWQwZGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJlNDggXHVjZTc4XHVjNzQwICYjMzk7LiYjMzk7XHVjNzNjXHViODVjLCBcdWMyMmJcdWM3OTAgXHVjZTc4XHVjNzQwIFx1Y2U3OFx1YzVkMCBcdWM0ZjBcdWM1ZWMgXHVjNzg4XHViMjk0IFx1YzIyYlx1Yzc5MFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Y2U3OFx1YzVkMCBcdWM0ZjBcdWM1ZWMgXHVjNzg4XHViMjk0IFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWQ1NmRcdWMwYzEgXHVkNTVjIFx1Yzc5MFx1YjlhY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgMFx1Yzc3NCBcdWI0NTAgXHVhYzFjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWQzN2NcdWM5OTBcdWM3NDQgXHVkNDdjIFx1YzBjMVx1ZDBkY1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YWM4MFx1YzgxNVx1Y2U3OFx1Yzc0MCAmIzM5OyMmIzM5O1x1YzczY1x1Yjg1YyBcdWQ0NWNcdWMyZGNcdWQ1NWNcdWIyZTQuIFx1ZDM3Y1x1Yzk5MFx1YWNmYyBcdWQzN2NcdWM5OTAgXHVjMGFjXHVjNzc0XHVjNWQwXHViMjk0IFx1YmU0OCBcdWM5MDRcdWM3NDQgXHVkNTU4XHViMDk4XHVjNTI5IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI2MjY4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTnVyaWthYmUiLCJkZXNjcmlwdGlvbiI6IjxwPllvdXIgZ29hbCBpcyB0byB3cml0ZSBhIHNvbHZlciBmb3IgTnVyaWthYmUsIGEgYmluYXJ5IGRldGVybWluYXRpb24gcHV6emxlLiBUaGUgcHV6emxlIGlzIHBsYXllZCBvbiBhIGdyaWQsIHR5cGljYWxseSByZWN0YW5ndWxhciAod2l0aCBubyBzdGFuZGFyZCBzaXplKSBjb250YWluaW5nIGVtcHR5IGFuZCBudW1iZXJlZCBjZWxscy4gWW91IG11c3QgZGVjaWRlIGZvciBlYWNoIGNlbGwgaWYgaXQgaXMgd2hpdGUgKGxhbmQpIG9yIGJsYWNrICh3YXRlciksIHNvIHRoYXQgaXQgc2F0aXNmaWVzIHRoZSBmb2xsb3dpbmcgY29uc3RyYWludHMuIEFuIElzbGFuZCBpcyBhIG1heGltYWwgY29ubmVjdGVkIHJlZ2lvbiBvZiB3aGl0ZSBjZWxscy4mbmJzcDs8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5UaGUgd2F0ZXIgYXJlYXMgbXVzdCBmb3JtIG9uZSBjb25uZWN0ZWQgcmVnaW9uLiAoQWxsIHRoZSBibGFjayBjZWxscyBtdXN0IGJlIGNvbm5lY3RlZC4pPFwvbGk+XHJcblx0PGxpPkVhY2ggbnVtYmVyZWQgY2VsbCBtdXN0IGJlIHBhcnQgb2YgYW4gaXNsYW5kLjxcL2xpPlxyXG5cdDxsaT5UaGUgbnVtYmVyIG9mIGNlbGxzIGluIGFuIGlzbGFuZCBpcyBlcXVhbCB0byB0aGUgbnVtYmVyIGl0IGNvbnRhaW5zLjxcL2xpPlxyXG5cdDxsaT5FdmVyeSByZWdpb24gKGlzbGFuZCkgb2Ygd2hpdGUgY2VsbHMgKGxhbmQpIG11c3QgY29udGFpbiBleGFjdGx5IG9uZSBudW1iZXIuPFwvbGk+XHJcblx0PGxpPlR3byBpc2xhbmRzIG1heSBub3QgYmUgY29ubmVjdGVkLjxcL2xpPlxyXG5cdDxsaT4yeDIgYmxvY2tzIG9mIGJsYWNrIHNxdWFyZXMgYXJlIG5vdCBhbGxvd2VkLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPk5vdGUgdGhhdCBkaWFnb25hbCBhZGphY2VuY3kgZG9lc24mIzM5O3QgY291bnQgYXMgY29ubmVjdGVkbmVzcy4gWW91IGNhbiBhc3N1bWUgdGhlcmUgaXMgYWx3YXlzIGEgdW5pcXVlIHNvbHV0aW9uIGZvciBlYWNoIHB1enpsZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9uMS5wbmdcIiBzdHlsZT1cImhlaWdodDoyNTdweDsgd2lkdGg6MjY5cHhcIiBcLz48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL24yLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjI1NnB4OyB3aWR0aDoyNjZweFwiIFwvPjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlcmUgYXJlIG11bHRpcGxlIHRlc3QgY2FzZXMgaW4gdGhlIGlucHV0LiBUaGUgZmlyc3QgbGluZSBvZiBlYWNoIHRlc3QgY2FzZSBjb250YWlucyB0d28gbnVtYmVycyBuLCBtICgzICZsZTsgbixtICZsZTsgOSkgd2hpY2ggYXJlIHRoZSBkaW1lbnNpb25zIG9mIHRoZSBwdXp6bGUsIGZvbGxvd2VkIGJ5IG4gbGluZXMgZWFjaCBvbmUgaGFzIG0gY2hhcmFjdGVycyBpbmNsdWRpbmcgJiMzOTsuJiMzOTsgKGluZGljYXRpbmcgYW4gZW1wdHkgY2VsbCkgYW5kIDEtZGlnaXQgbnVtYmVycy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGxhc3QgbGluZSBvZiB0aGUgaW5wdXQgY29udGFpbnMgdHdvIHplcm8gbnVtYmVycy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb3V0cHV0IGZvciBlYWNoIHRlc3QgY2FzZSBzaG91bGQgc2hvdyB0aGUgc29sdmVkIHB1enpsZS4gU2hvdyBibGFjayAod2F0ZXIpIGNlbGxzIHdpdGggJiMzOTsjJiMzOTsuIFdyaXRlIGFuIGVtcHR5IGxpbmUgaW4gdGhlIG91dHB1dCBhZnRlciBlYWNoIHB1enpsZS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

ACM-ICPC > Regionals > Asia > Iran > Tehran Site 2007 J번