시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 40 6 5 25.000%

문제

0과 1로 차 있는 n×m 크기의 격자가 있다. 뱀은 1들의 연속이라고 볼 수 있다. 구체적으로 정의하자면 뱀은 이 격자 안에서 다음과 같은 조건을 만족하는 것이다.

  1. 1이 들어 있는 칸을 뱀 격자라고 한다.
  2. 뱀의 시작점과 끝점을 제외하고는 뱀 안에 있는 뱀 격자는 동서남북 방향으로 두 개의 뱀 격자와 만난다. 뱀의 양 끝점은 한 개의 뱀 격자와 만난다고 가정하여도 좋다.

그리고 maximal snake란, 위의 조건을 만족하는 뱀들 중, 뱀의 양 끝 중 한 군데에 1을 추가시킨다면 더 이상 위의 조건을 만족시키지 않는 뱀을 의미한다. 예를 들면 아래 그림에서 가장 왼쪽에 있는 곳에서는 하나의 maximal snake가 있고, 두 번째에는 maximal snake가 없으며 세 번째에는 세 개의 maximal snake가 있다.

n×m 격자가 주어져 있을 때, 몇 개의 maximal snake가 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n, m(1 ≤ n,m ≤ 200) 이 주어진다. 그리고 n+1줄에 걸쳐 격자의 정보가 주어진다.

출력

첫째 줄에 maximal snake의 수를 출력하시오.

예제 입력 1

7 10
1111111110
0000000010
1100000011
1011110001
1010010001
1010010111
1110011100

예제 출력 1

1
W3sicHJvYmxlbV9pZCI6IjIwMzkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjNDAgXHVjYzNlXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD4wXHVhY2ZjIDFcdWI4NWMgXHVjYzI4IFx1Yzc4OFx1YjI5NCBuJnRpbWVzO20gXHVkMDZjXHVhZTMwXHVjNzU4IFx1YWNhOVx1Yzc5MFx1YWMwMCBcdWM3ODhcdWIyZTQuIFx1YmM0MFx1Yzc0MCAxXHViNGU0XHVjNzU4IFx1YzVmMFx1YzE4ZFx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWJjZmMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhZDZjXHVjY2I0XHVjODAxXHVjNzNjXHViODVjIFx1YzgxNVx1Yzc1OFx1ZDU1OFx1Yzc5MFx1YmE3NCBcdWJjNDBcdWM3NDAgXHVjNzc0IFx1YWNhOVx1Yzc5MCBcdWM1NDhcdWM1ZDBcdWMxMWMgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT4xXHVjNzc0IFx1YjRlNFx1YzViNCBcdWM3ODhcdWIyOTQgXHVjZTc4XHVjNzQ0IFx1YmM0MCBcdWFjYTlcdWM3OTBcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWJjNDBcdWM3NTggXHVjMmRjXHVjNzkxXHVjODEwXHVhY2ZjIFx1YjA1ZFx1YzgxMFx1Yzc0NCBcdWM4MWNcdWM2NzhcdWQ1NThcdWFjZTBcdWIyOTQgXHViYzQwIFx1YzU0OFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViYzQwIFx1YWNhOVx1Yzc5MFx1YjI5NCBcdWIzZDlcdWMxMWNcdWIwYThcdWJkODEgXHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1YjQ1MCBcdWFjMWNcdWM3NTggXHViYzQwIFx1YWNhOVx1Yzc5MFx1YzY0MCBcdWI5Y2NcdWIwOWNcdWIyZTQuIFx1YmM0MFx1Yzc1OCBcdWM1OTEgXHViMDVkXHVjODEwXHVjNzQwIFx1ZDU1YyBcdWFjMWNcdWM3NTggXHViYzQwIFx1YWNhOVx1Yzc5MFx1YzY0MCBcdWI5Y2NcdWIwOWNcdWIyZTRcdWFjZTAgXHVhYzAwXHVjODE1XHVkNTU4XHVjNWVjXHViM2M0IFx1Yzg4Ylx1YjJlNC48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5cdWFkZjhcdWI5YWNcdWFjZTAgbWF4aW1hbCBzbmFrZVx1Yjc4MCwgXHVjNzA0XHVjNzU4IFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHViYzQwXHViNGU0IFx1YzkxMSwgXHViYzQwXHVjNzU4IFx1YzU5MSBcdWIwNWQgXHVjOTExIFx1ZDU1YyBcdWFkNzBcdWIzNzBcdWM1ZDAgMVx1Yzc0NCBcdWNkOTRcdWFjMDBcdWMyZGNcdWQwYThcdWIyZTRcdWJhNzQgXHViMzU0IFx1Yzc3NFx1YzBjMSBcdWM3MDRcdWM3NTggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1YzJkY1x1ZDBhNFx1YzljMCBcdWM1NGFcdWIyOTQgXHViYzQwXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YmE3NCBcdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWM2N2NcdWNhYmRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YWNmM1x1YzVkMFx1YzExY1x1YjI5NCBcdWQ1NThcdWIwOThcdWM3NTggbWF4aW1hbCBzbmFrZVx1YWMwMCBcdWM3ODhcdWFjZTAsIFx1YjQ1MCBcdWJjODhcdWM5ZjhcdWM1ZDBcdWIyOTQgbWF4aW1hbCBzbmFrZVx1YWMwMCBcdWM1YzZcdWM3M2NcdWJhNzAgXHVjMTM4IFx1YmM4OFx1YzlmOFx1YzVkMFx1YjI5NCBcdWMxMzggXHVhYzFjXHVjNzU4IG1heGltYWwgc25ha2VcdWFjMDAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIGhlaWdodD1cIjEzOFwiIHNyYz1cIlwvSnVkZ2VPbmxpbmVcL3VwbG9hZFwvMjAxMDA3XC9zbmsucG5nXCIgd2lkdGg9XCI1NjdcIiBcLz48XC9wPlxyXG5cclxuPHA+biZ0aW1lczttIFx1YWNhOVx1Yzc5MFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4MzggXHVjNzg4XHVjNzQ0IFx1YjU0YywgXHViYTg3IFx1YWMxY1x1Yzc1OCBtYXhpbWFsIHNuYWtlXHVhYzAwIFx1Yzc4OFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgbiwgbSgxICZsZTsgbixtICZsZTsgMjAwKSBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgbisxXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMCBcdWFjYTlcdWM3OTBcdWM3NTggXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIG1heGltYWwgc25ha2VcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyMDM5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU25ha2VzIG9uIGEgUGxhbmUiLCJkZXNjcmlwdGlvbiI6IjxwPkFzc3VtZSB3ZSBoYXZlIGFuIG4mdGltZXM7bSBncmlkIG9mIHNxdWFyZXMsIGVhY2ggZmlsbGVkIHdpdGggZWl0aGVyIDAgb3IgMS4gQSBzbmFrZSBpcyBhIGNvbm5lY3RlZCBzZXF1ZW5jZSBvZiBncmlkIHNxdWFyZXMgd2hpY2ggaGFzIHRoZSBmb2xsb3dpbmcgcHJvcGVydGllczo8XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5FYWNoIHNuYWtlIHNxdWFyZSBoYXMgYSAxIGluIGl0PFwvbGk+XHJcblx0PGxpPkVhY2ggc25ha2Ugc3F1YXJlIHRvdWNoZXMgZXhhY3RseSB0d28gb3RoZXIgc25ha2Ugc3F1YXJlcyAobm9ydGhcL3NvdXRoXC9lYXN0XC93ZXN0KSwgZXhjZXB0IHRoZSBmaXJzdCBhbmQgbGFzdCBzcXVhcmUgaW4gdGhlIHNlcXVlbmNlICh0aGUgaGVhZCBhbmQgdGFpbCBvZiB0aGUgc25ha2UpPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+QSBtYXhpbWFsIHNuYWtlIGlzIG9uZSBpbiB3aGljaCB3ZSBjYW5ub3QgYWRkIGEgMSB0byBlaXRoZXIgZW5kIHdpdGhvdXQgZWl0aGVyIGxlbmd0aGVuaW5nIHRoZSBzbmFrZSwgY29tYmluaW5nIHR3byBzbmFrZXMgdG9nZXRoZXIsIG9yIHZpb2xhdGluZyBydWxlIDIgYWJvdmUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBleGFtcGxlcyBiZWxvdyBzaG93IGdyaWRzIHdpdGggYW5kIHdpdGhvdXQgbWF4aW1hbCBzbmFrZXMgKGFsbCBlbXB0eSBzcXVhcmVzIGhhdmUgMCZyc3F1bztzIGluIHRoZW0pLiBOb3RpY2UgdGhhdCB0aGUgc2Vjb25kIGdyaWQgZG9lcyBub3QgaGF2ZSBhIG1heGltYWwgc25ha2Ugc2luY2UgeW91IGNhbiBhZGQgYSAxIGF0IHRoZSBlbmQgb2YgZWl0aGVyIHNuYWtlIHRvIGdldCBhIGxhcmdlciBzbmFrZS48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9zbmFrZXBsYS5wbmdcIiBzdHlsZT1cImhlaWdodDoxMzFweDsgd2lkdGg6NTE1cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+Rm9yIHRoaXMgcHJvYmxlbSwgeW91IHdpbGwgYmUgZ2l2ZW4gZ3JpZHMgYW5kIG11c3QgY291bnQgdGhlIG51bWJlciBvZiBtYXhpbWFsIHNuYWtlcyBpbiBlYWNoLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+SW5wdXQgd2lsbCBjb25zaXN0IG9mIG11bHRpcGxlIHRlc3QgY2FzZXMuIFRoZSBcdWZiMDFyc3QgbGluZSBvZiBlYWNoIHRlc3QgY2FzZSB3aWxsIGNvbnRhaW4gdHdvIHBvc2l0aXZlIGludGVnZXJzIG4gbSBpbmRpY2F0aW5nIHRoZSBudW1iZXIgb2Ygcm93cyBhbmQgY29sdW1ucyBpbiB0aGUgZ3JpZCAodGhlIG1heGltdW0gdmFsdWUgb2YgZWFjaCB3aWxsIGJlIDIwMCkuIFRoZSBuZXh0IG4gbGluZXMgd2lsbCBjb25zaXN0IG9mIG0gY2hhcmFjdGVycyAoZWl0aGVyICZyc3F1bzswJnJzcXVvOyBvciAmcnNxdW87MSZyc3F1bzspIHNwZWNpZnlpbmcgdGhlIGdyaWQuIFRoZSBsYXN0IGNhc2UgaXMgZm9sbG93ZWQgYnkgYSBsaW5lIGNvbnRhaW5pbmcgMCAwIHdoaWNoIGluZGljYXRlcyBlbmQtb2YtaW5wdXQgYW5kIHNob3VsZCBub3QgYmUgcHJvY2Vzc2VkLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgb3V0cHV0IGEgc2luZ2xlIGxpbmUgY29udGFpbmluZyB0aGUgbnVtYmVyIG9mIG1heGltYWwgc25ha2VzIGluIHRoZSBncmlkPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d