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

문제

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.

둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.

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

출력

각 테스트 케이스에 대해서, 섬의 개수를 출력한다.

예제 입력 1

1 1
0
2 2
0 1
1 0
3 2
1 1 1
1 1 1
5 4
1 0 1 0 0
1 0 0 0 0
1 0 1 0 1
1 0 0 1 0
5 4
1 1 1 0 1
1 0 1 0 1
1 0 1 0 1
1 0 1 1 1
5 5
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0

예제 출력 1

0
1
1
3
1
9
W3sicHJvYmxlbV9pZCI6IjQ5NjMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxMmNcdWM3NTggXHVhYzFjXHVjMjE4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjI5NCBcdWMxMmNcdWFjZmMgXHViYzE0XHViMmU0IFx1YzljMFx1YjNjNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzEyY1x1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjMTM4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvaXNsYW5kLnBuZ1wiIHN0eWxlPVwid2lkdGg6IDI4M3B4OyBoZWlnaHQ6IDE0MXB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5cdWQ1NWMgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVhY2ZjIFx1YWMwMFx1Yjg1YywgXHVjMTM4XHViODVjIFx1YjYxMFx1YjI5NCBcdWIzMDBcdWFjMDFcdWMxMjBcdWM3M2NcdWI4NWMgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjI5NCBcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDAgXHVhYzc4XHVjNWI0XHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzc0XHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzc0IFx1YWMxOVx1Yzc0MCBcdWMxMmNcdWM1ZDAgXHVjNzg4XHVjNzNjXHViODI0XHViYTc0LCBcdWQ1NWMgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNWQwXHVjMTFjIFx1YjJlNFx1Yjk3OCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3M2NcdWI4NWMgXHVhYzc4XHVjNWI0XHVjMTFjIFx1YWMwOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWNiZFx1Yjg1Y1x1YWMwMCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWM5YzBcdWIzYzRcdWIyOTQgXHViYzE0XHViMmU0XHViODVjIFx1YjQ1OFx1YjdlY1x1YzJmOFx1YzVlYyBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YzljMFx1YjNjNCBcdWJjMTZcdWM3M2NcdWI4NWMgXHViMDk4XHVhYzA4IFx1YzIxOCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjOWMwXHViM2M0XHVjNzU4IFx1YjEwOFx1YmU0NCB3XHVjNjQwIFx1YjE5Mlx1Yzc3NCBoXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gd1x1YzY0MCBoXHViMjk0IDUwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBoXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM5YzBcdWIzYzRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAxXHVjNzQwIFx1YjU0NSwgMFx1Yzc0MCBcdWJjMTRcdWIyZTRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IDBcdWM3NzQgXHViNDUwIFx1YWMxYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWMxMmNcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0OTYzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiSG93IE1hbnkgSXNsYW5kcz8iLCJkZXNjcmlwdGlvbiI6IjxwPllvdSBhcmUgZ2l2ZW4gYSBtYXJpbmUgYXJlYSBtYXAgdGhhdCBpcyBhIG1lc2ggb2Ygc3F1YXJlcywgZWFjaCByZXByZXNlbnRpbmcgZWl0aGVyIGEgbGFuZCBvciBzZWEgYXJlYS4gRmlndXJlIEItMSBpcyBhbiBleGFtcGxlIG9mIGEgbWFwLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2lzbGFuZC5wbmdcIiBzdHlsZT1cImhlaWdodDoxNDFweDsgd2lkdGg6MjgzcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+RmlndXJlIEItMTogQSBtYXJpbmUgYXJlYSBtYXA8XC9wPlxyXG5cclxuPHA+WW91IGNhbiB3YWxrIGZyb20gYSBzcXVhcmUgbGFuZCBhcmVhIHRvIGFub3RoZXIgaWYgdGhleSBhcmUgaG9yaXpvbnRhbGx5LCB2ZXJ0aWNhbGx5LCBvciBkaWFnb25hbGx5IGFkamFjZW50IHRvIGVhY2ggb3RoZXIgb24gdGhlIG1hcC4gVHdvIGFyZWFzIGFyZSBvbiB0aGUgc2FtZSBpc2xhbmQgaWYgYW5kIG9ubHkgaWYgeW91IGNhbiB3YWxrIGZyb20gb25lIHRvIHRoZSBvdGhlciBwb3NzaWJseSB0aHJvdWdoIG90aGVyIGxhbmQgYXJlYXMuIFRoZSBtYXJpbmUgYXJlYSBvbiB0aGUgbWFwIGlzIHN1cnJvdW5kZWQgYnkgdGhlIHNlYSBhbmQgdGhlcmVmb3JlIHlvdSBjYW5ub3QgZ28gb3V0c2lkZSBvZiB0aGUgYXJlYSBvbiBmb290LjxcL3A+XHJcblxyXG48cD5Zb3UgYXJlIHJlcXVlc3RlZCB0byB3cml0ZSBhIHByb2dyYW0gdGhhdCByZWFkcyB0aGUgbWFwIGFuZCBjb3VudHMgdGhlIG51bWJlciBvZiBpc2xhbmRzIG9uIGl0LiBGb3IgaW5zdGFuY2UsIHRoZSBtYXAgaW4gRmlndXJlIEItMSBpbmNsdWRlcyB0aHJlZSBpc2xhbmRzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnNpc3RzIG9mIGEgc2VyaWVzIG9mIGRhdGFzZXRzLCBlYWNoIGJlaW5nIGluIHRoZSBmb2xsb3dpbmcgZm9ybWF0LjxcL3A+XHJcblxyXG48cD53IGg8YnIgXC8+XHJcbmMxLDEgYzEsMiAuLi4gYzEsdzxiciBcLz5cclxuYzIsMSBjMiwyIC4uLiBjMix3PGJyIFwvPlxyXG4uLi48YnIgXC8+XHJcbmNoLDEgY2gsMiAuLi4gY2gsdzxcL3A+XHJcblxyXG48cD53IGFuZCBoIGFyZSBwb3NpdGl2ZSBpbnRlZ2VycyBubyBtb3JlIHRoYW4gNTAgdGhhdCByZXByZXNlbnQgdGhlIHdpZHRoIGFuZCB0aGUgaGVpZ2h0IG9mIHRoZSBnaXZlbiBtYXAsIHJlc3BlY3RpdmVseS4gSW4gb3RoZXIgd29yZHMsIHRoZSBtYXAgY29uc2lzdHMgb2YgdyZ0aW1lcztoIHNxdWFyZXMgb2YgdGhlIHNhbWUgc2l6ZS4gdyBhbmQgaCBhcmUgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlLjxcL3A+XHJcblxyXG48cD5jaSwgaiBpcyBlaXRoZXIgMCBvciAxIGFuZCBkZWxpbWl0ZWQgYnkgYSBzaW5nbGUgc3BhY2UuIElmIGNpLCBqID0gMCwgdGhlIHNxdWFyZSB0aGF0IGlzIHRoZSBpLXRoIGZyb20gdGhlIGxlZnQgYW5kIGotdGggZnJvbSB0aGUgdG9wIG9uIHRoZSBtYXAgcmVwcmVzZW50cyBhIHNlYSBhcmVhLiBPdGhlcndpc2UsIHRoYXQgaXMsIGlmIGNpLCBqID0gMSwgaXQgcmVwcmVzZW50cyBhIGxhbmQgYXJlYS48XC9wPlxyXG5cclxuPHA+VGhlIGVuZCBvZiB0aGUgaW5wdXQgaXMgaW5kaWNhdGVkIGJ5IGEgbGluZSBjb250YWluaW5nIHR3byB6ZXJvcyBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2U8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBkYXRhc2V0LCBvdXRwdXQgdGhlIG51bWJlciBvZiB0aGUgaXNsYW5kcyBpbiBhIGxpbmUuIE5vIGV4dHJhIGNoYXJhY3RlcnMgc2hvdWxkIG9jY3VyIGluIHRoZSBvdXRwdXQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

ICPC > Regionals > Asia Pacific > Japan > Japan Domestic Contest > 2009 Japan Domestic Contest B번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: j4bez