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

문제

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

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

  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
W3sicHJvYmxlbV9pZCI6IjYyNjgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIyMDRcdWI5YWNcdWNlNzRcdWJjYTAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDc2Y1x1YzZkMFx1Yzc3NFx1YjI5NCBcdWIyMDRcdWI5YWNcdWNlNzRcdWJjYTAgXHVkMzdjXHVjOTkwXHVjNzQ0IFx1ZDQ3OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHViOWNjXHViNGU0XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMjA0XHViOWFjXHVjZTc0XHViY2EwIFx1ZDM3Y1x1Yzk5MFx1Yzc0MCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUgXHVhZGY4XHViOWFjXHViNGRjIFx1YzBjMVx1YzVkMFx1YzExYyBcdWM5YzRcdWQ1ODlcdWI0MThcdWJhNzAsIFx1YmU0OCBcdWNlNzhcdWFjZmMgXHVjMjJiXHVjNzkwXHVhYzAwIFx1YjRlNFx1YzViNFx1Yzc4OFx1YjI5NCBcdWNlNzhcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1ZDQ4MFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWNcdWIyOTQgXHVhYzAxIFx1Y2U3OFx1Yzc3NCBcdWM1NDRcdWI3OThcdWM3NTggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1YzJkY1x1ZDBhNFx1YjgyNFx1YmE3NCwgXHVkNzcwXHVjMGM5KFx1YjU0NSlcdWM3NzQgXHViNDIwXHVjOWMwIFx1YWM4MFx1YzgxNVx1YzBjOShcdWJjMTRcdWIyZTQpXHVhYzAwIFx1YjQyMFx1YzljMCBcdWFjYjBcdWM4MTVcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWMxMmNcdWM3NDAgXHVkNzcwIFx1Y2U3OFx1YzczY1x1Yjg1YyBcdWNkNWNcdWIzMDBcdWQ1NWMgXHVjNWYwXHVhY2IwXHViNDFjIFx1YWQ2Y1x1YzVlZFx1Yzc0NCBcdWI5ZDBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+XHVhYzgwXHVjODE1XHVjMGM5IFx1Y2U3OFx1Yzc0MCBcdWJhYThcdWI0NTAgXHVjMTFjXHViODVjIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT4mbmJzcDtcdWMyMmJcdWM3OTBcdWFjMDAgXHVjNGYwXHVjNWVjIFx1Yzc4OFx1YjI5NCBcdWNlNzhcdWM3NDAgXHVkNTZkXHVjMGMxIFx1YzEyY1x1Yzc1OCBcdWM3N2NcdWJkODBcdWM3NzRcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWMxMmNcdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDE4XHVjNWI0IFx1Yzc4OFx1YjI5NCBcdWNlNzhcdWM3NTggXHVhYzFjXHVjMjE4XHViMjk0IFx1YWRmOCBcdWMxMmNcdWM3NzQgXHVkM2VjXHVkNTY4XHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWMyMmJcdWM3OTAgXHVjZTc4XHVjNzU4IFx1YzIyYlx1Yzc5MFx1YzY0MCBcdWFjMTlcdWM1NDRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWJhYThcdWI0ZTAgXHVjMTJjXHVjNWQwXHViMjk0IFx1YzIyYlx1Yzc5MCBcdWNlNzhcdWM3NzQgXHVkNTU4XHViMDk4IFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YjQ1MCBcdWMxMmNcdWM3NDAgXHVjMTFjXHViODVjIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWM3M2NcdWJhNzQgXHVjNTQ4IFx1YjQxY1x1YjJlNC48XC9saT5cclxuXHQ8bGk+MiZ0aW1lczsyIFx1YmFhOFx1YzU5MVx1Yzc1OCBcdWFjODBcdWM4MTVcdWNlNzhcdWM3NDAgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM1YzZcdWIyZTQuPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+XHVjZTc4XHVjNzQwIFx1YjMwMFx1YWMwMVx1YzEyMFx1YzczY1x1Yjg1YyBcdWM1ZjBcdWFjYjBcdWI0MjAgXHVjMjE4IFx1YzVjNlx1YjJlNC4gXHVkNTZkXHVjMGMxIFx1YjJmNVx1Yzc3NCBcdWM3MjBcdWM3N2NcdWQ1NWMgXHVhY2JkXHVjNmIwXHViOWNjIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvbjEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjU3cHg7IHdpZHRoOjI2OXB4XCIgXC8+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9uMi5wbmdcIiBzdHlsZT1cImhlaWdodDoyNTZweDsgd2lkdGg6MjY2cHhcIiBcLz48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQzN2NcdWM5OTBcdWM3NTggXHVkMDZjXHVhZTMwIG5cdWFjZmMgbVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgzICZsZTsgbiwgbSAmbGU7IDkpPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBuXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQzN2NcdWM5OTBcdWM3NTggXHVjZDA4XHVhZTMwIFx1YzBjMVx1ZDBkY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YmU0OCBcdWNlNzhcdWM3NDAgJiMzOTsuJiMzOTtcdWM3M2NcdWI4NWMsIFx1YzIyYlx1Yzc5MCBcdWNlNzhcdWM3NDAgXHVjZTc4XHVjNWQwIFx1YzRmMFx1YzVlYyBcdWM3ODhcdWIyOTQgXHVjMjJiXHVjNzkwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjZTc4XHVjNWQwIFx1YzRmMFx1YzVlYyBcdWM3ODhcdWIyOTQgXHVjMjJiXHVjNzkwXHViMjk0IFx1ZDU2ZFx1YzBjMSBcdWQ1NWMgXHVjNzkwXHViOWFjXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAwXHVjNzc0IFx1YjQ1MCBcdWFjMWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1ZDM3Y1x1Yzk5MFx1Yzc0NCBcdWQ0N2MgXHVjMGMxXHVkMGRjXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVhYzgwXHVjODE1XHVjZTc4XHVjNzQwICYjMzk7IyYjMzk7XHVjNzNjXHViODVjIFx1ZDQ1Y1x1YzJkY1x1ZDU1Y1x1YjJlNC4gXHVkMzdjXHVjOTkwXHVhY2ZjIFx1ZDM3Y1x1Yzk5MCBcdWMwYWNcdWM3NzRcdWM1ZDBcdWIyOTQgXHViZTQ4IFx1YzkwNFx1Yzc0NCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjYyNjgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJOdXJpa2FiZSIsImRlc2NyaXB0aW9uIjoiPHA+WW91ciBnb2FsIGlzIHRvIHdyaXRlIGEgc29sdmVyIGZvciBOdXJpa2FiZSwgYSBiaW5hcnkgZGV0ZXJtaW5hdGlvbiBwdXp6bGUuIFRoZSBwdXp6bGUgaXMgcGxheWVkIG9uIGEgZ3JpZCwgdHlwaWNhbGx5IHJlY3Rhbmd1bGFyICh3aXRoIG5vIHN0YW5kYXJkIHNpemUpIGNvbnRhaW5pbmcgZW1wdHkgYW5kIG51bWJlcmVkIGNlbGxzLiBZb3UgbXVzdCBkZWNpZGUgZm9yIGVhY2ggY2VsbCBpZiBpdCBpcyB3aGl0ZSAobGFuZCkgb3IgYmxhY2sgKHdhdGVyKSwgc28gdGhhdCBpdCBzYXRpc2ZpZXMgdGhlIGZvbGxvd2luZyBjb25zdHJhaW50cy4gQW4gSXNsYW5kIGlzIGEgbWF4aW1hbCBjb25uZWN0ZWQgcmVnaW9uIG9mIHdoaXRlIGNlbGxzLiZuYnNwOzxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlRoZSB3YXRlciBhcmVhcyBtdXN0IGZvcm0gb25lIGNvbm5lY3RlZCByZWdpb24uIChBbGwgdGhlIGJsYWNrIGNlbGxzIG11c3QgYmUgY29ubmVjdGVkLik8XC9saT5cclxuXHQ8bGk+RWFjaCBudW1iZXJlZCBjZWxsIG11c3QgYmUgcGFydCBvZiBhbiBpc2xhbmQuPFwvbGk+XHJcblx0PGxpPlRoZSBudW1iZXIgb2YgY2VsbHMgaW4gYW4gaXNsYW5kIGlzIGVxdWFsIHRvIHRoZSBudW1iZXIgaXQgY29udGFpbnMuPFwvbGk+XHJcblx0PGxpPkV2ZXJ5IHJlZ2lvbiAoaXNsYW5kKSBvZiB3aGl0ZSBjZWxscyAobGFuZCkgbXVzdCBjb250YWluIGV4YWN0bHkgb25lIG51bWJlci48XC9saT5cclxuXHQ8bGk+VHdvIGlzbGFuZHMgbWF5IG5vdCBiZSBjb25uZWN0ZWQuPFwvbGk+XHJcblx0PGxpPjJ4MiBibG9ja3Mgb2YgYmxhY2sgc3F1YXJlcyBhcmUgbm90IGFsbG93ZWQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Tm90ZSB0aGF0IGRpYWdvbmFsIGFkamFjZW5jeSBkb2VzbiYjMzk7dCBjb3VudCBhcyBjb25uZWN0ZWRuZXNzLiBZb3UgY2FuIGFzc3VtZSB0aGVyZSBpcyBhbHdheXMgYSB1bmlxdWUgc29sdXRpb24gZm9yIGVhY2ggcHV6emxlLiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL24xLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjI1N3B4OyB3aWR0aDoyNjlweFwiIFwvPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvbjIucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjU2cHg7IHdpZHRoOjI2NnB4XCIgXC8+PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGVyZSBhcmUgbXVsdGlwbGUgdGVzdCBjYXNlcyBpbiB0aGUgaW5wdXQuIFRoZSBmaXJzdCBsaW5lIG9mIGVhY2ggdGVzdCBjYXNlIGNvbnRhaW5zIHR3byBudW1iZXJzIG4sIG0gKDMgJmxlOyBuLG0gJmxlOyA5KSB3aGljaCBhcmUgdGhlIGRpbWVuc2lvbnMgb2YgdGhlIHB1enpsZSwgZm9sbG93ZWQgYnkgbiBsaW5lcyBlYWNoIG9uZSBoYXMgbSBjaGFyYWN0ZXJzIGluY2x1ZGluZyAmIzM5Oy4mIzM5OyAoaW5kaWNhdGluZyBhbiBlbXB0eSBjZWxsKSBhbmQgMS1kaWdpdCBudW1iZXJzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgbGFzdCBsaW5lIG9mIHRoZSBpbnB1dCBjb250YWlucyB0d28gemVybyBudW1iZXJzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBvdXRwdXQgZm9yIGVhY2ggdGVzdCBjYXNlIHNob3VsZCBzaG93IHRoZSBzb2x2ZWQgcHV6emxlLiBTaG93IGJsYWNrICh3YXRlcikgY2VsbHMgd2l0aCAmIzM5OyMmIzM5Oy4gV3JpdGUgYW4gZW1wdHkgbGluZSBpbiB0aGUgb3V0cHV0IGFmdGVyIGVhY2ggcHV6emxlLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

ICPC > Regionals > Asia West Continent > Iran > Tehran Site 2007 J번