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

문제

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

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

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

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 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

힌트

W3sicHJvYmxlbV9pZCI6IjQ5NjMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxMmNcdWM3NTggXHVhYzFjXHVjMjE4IiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjI5NCBcdWMxMmNcdWFjZmMgXHViYzE0XHViMmU0IFx1YzljMFx1YjNjNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzEyY1x1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjMTM4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdDxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvaXNsYW5kLnBuZ1wiIHN0eWxlPVwid2lkdGg6IDI4M3B4OyBoZWlnaHQ6IDE0MXB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWQ1NWMgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVhY2ZjIFx1YWMwMFx1Yjg1YywgXHVjMTM4XHViODVjIFx1YjYxMFx1YjI5NCBcdWIzMDBcdWFjMDFcdWMxMjBcdWM3M2NcdWI4NWMgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjI5NCBcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDAgXHVhYzc4XHVjNWI0XHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzc0XHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cclxuXHRcdWI0NTAgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzc0IFx1YWMxOVx1Yzc0MCBcdWMxMmNcdWM1ZDAgXHVjNzg4XHVjNzNjXHViODI0XHViYTc0LCBcdWQ1NWMgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNWQwXHVjMTFjIFx1YjJlNFx1Yjk3OCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3M2NcdWI4NWMgXHVhYzc4XHVjNWI0XHVjMTFjIFx1YWMwOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWNiZFx1Yjg1Y1x1YWMwMCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWM5YzBcdWIzYzRcdWIyOTQgXHViYzE0XHViMmU0XHViODVjIFx1YjQ1OFx1YjdlY1x1YzMxM1x1YzVlYyBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YzljMFx1YjNjNCBcdWJjMTZcdWM3M2NcdWI4NWMgXHViMDk4XHVhYzA4IFx1YzIxOCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiJcclxuPHA+XHJcblx0XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzljMFx1YjNjNFx1Yzc1OCBcdWIxMDhcdWJlNDQgd1x1YzY0MCBcdWIxOTJcdWM3NzQgaFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIHdcdWM2NDAgaFx1YjI5NCA1MFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgaFx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjOWMwXHViM2M0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gMVx1Yzc0MCBcdWI1NDUsIDBcdWM3NDAgXHViYzE0XHViMmU0XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAwXHVjNzc0IFx1YjQ1MCBcdWFjMWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVjMTJjXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNDk2MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkhvdyBNYW55IElzbGFuZHM/IiwiZGVzY3JpcHRpb24iOiI8cD5Zb3UgYXJlIGdpdmVuIGEgbWFyaW5lIGFyZWEgbWFwIHRoYXQgaXMgYSBtZXNoIG9mIHNxdWFyZXMsIGVhY2ggcmVwcmVzZW50aW5nIGVpdGhlciBhIGxhbmQgb3Igc2VhIGFyZWEuIEZpZ3VyZSBCLTEgaXMgYW4gZXhhbXBsZSBvZiBhIG1hcC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9pc2xhbmQucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTQxcHg7IHdpZHRoOjI4M3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkZpZ3VyZSBCLTE6IEEgbWFyaW5lIGFyZWEgbWFwPFwvcD5cclxuXHJcbjxwPllvdSBjYW4gd2FsayBmcm9tIGEgc3F1YXJlIGxhbmQgYXJlYSB0byBhbm90aGVyIGlmIHRoZXkgYXJlIGhvcml6b250YWxseSwgdmVydGljYWxseSwgb3IgZGlhZ29uYWxseSBhZGphY2VudCB0byBlYWNoIG90aGVyIG9uIHRoZSBtYXAuIFR3byBhcmVhcyBhcmUgb24gdGhlIHNhbWUgaXNsYW5kIGlmIGFuZCBvbmx5IGlmIHlvdSBjYW4gd2FsayBmcm9tIG9uZSB0byB0aGUgb3RoZXIgcG9zc2libHkgdGhyb3VnaCBvdGhlciBsYW5kIGFyZWFzLiBUaGUgbWFyaW5lIGFyZWEgb24gdGhlIG1hcCBpcyBzdXJyb3VuZGVkIGJ5IHRoZSBzZWEgYW5kIHRoZXJlZm9yZSB5b3UgY2Fubm90IGdvIG91dHNpZGUgb2YgdGhlIGFyZWEgb24gZm9vdC48XC9wPlxyXG5cclxuPHA+WW91IGFyZSByZXF1ZXN0ZWQgdG8gd3JpdGUgYSBwcm9ncmFtIHRoYXQgcmVhZHMgdGhlIG1hcCBhbmQgY291bnRzIHRoZSBudW1iZXIgb2YgaXNsYW5kcyBvbiBpdC4gRm9yIGluc3RhbmNlLCB0aGUgbWFwIGluIEZpZ3VyZSBCLTEgaW5jbHVkZXMgdGhyZWUgaXNsYW5kcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb25zaXN0cyBvZiBhIHNlcmllcyBvZiBkYXRhc2V0cywgZWFjaCBiZWluZyBpbiB0aGUgZm9sbG93aW5nIGZvcm1hdC48XC9wPlxyXG5cclxuPHA+dyBoPGJyIFwvPlxyXG5jMSwxIGMxLDIgLi4uIGMxLHc8YnIgXC8+XHJcbmMyLDEgYzIsMiAuLi4gYzIsdzxiciBcLz5cclxuLi4uPGJyIFwvPlxyXG5jaCwxIGNoLDIgLi4uIGNoLHc8XC9wPlxyXG5cclxuPHA+dyBhbmQgaCBhcmUgcG9zaXRpdmUgaW50ZWdlcnMgbm8gbW9yZSB0aGFuIDUwIHRoYXQgcmVwcmVzZW50IHRoZSB3aWR0aCBhbmQgdGhlIGhlaWdodCBvZiB0aGUgZ2l2ZW4gbWFwLCByZXNwZWN0aXZlbHkuIEluIG90aGVyIHdvcmRzLCB0aGUgbWFwIGNvbnNpc3RzIG9mIHcmdGltZXM7aCBzcXVhcmVzIG9mIHRoZSBzYW1lIHNpemUuIHcgYW5kIGggYXJlIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZS48XC9wPlxyXG5cclxuPHA+Y2ksIGogaXMgZWl0aGVyIDAgb3IgMSBhbmQgZGVsaW1pdGVkIGJ5IGEgc2luZ2xlIHNwYWNlLiBJZiBjaSwgaiA9IDAsIHRoZSBzcXVhcmUgdGhhdCBpcyB0aGUgaS10aCBmcm9tIHRoZSBsZWZ0IGFuZCBqLXRoIGZyb20gdGhlIHRvcCBvbiB0aGUgbWFwIHJlcHJlc2VudHMgYSBzZWEgYXJlYS4gT3RoZXJ3aXNlLCB0aGF0IGlzLCBpZiBjaSwgaiA9IDEsIGl0IHJlcHJlc2VudHMgYSBsYW5kIGFyZWEuPFwvcD5cclxuXHJcbjxwPlRoZSBlbmQgb2YgdGhlIGlucHV0IGlzIGluZGljYXRlZCBieSBhIGxpbmUgY29udGFpbmluZyB0d28gemVyb3Mgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggZGF0YXNldCwgb3V0cHV0IHRoZSBudW1iZXIgb2YgdGhlIGlzbGFuZHMgaW4gYSBsaW5lLiBObyBleHRyYSBjaGFyYWN0ZXJzIHNob3VsZCBvY2N1ciBpbiB0aGUgb3V0cHV0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==