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

문제

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
W3sicHJvYmxlbV9pZCI6IjIwMzkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjNDAgXHVjYzNlXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD4wXHVhY2ZjIDFcdWI4NWMgXHVjYzI4XHVjNzg4XHViMjk0IG4qbSBcdWQwNmNcdWFlMzBcdWM3NTggXHVhY2E5XHVjNzkwXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHViYzQwXHVjNzQwIDFcdWI0ZTRcdWM3NTggXHVjNWYwXHVjMThkXHVjNzc0XHViNzdjXHVhY2UwIFx1YmNmYyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWFkNmNcdWNjYjRcdWM4MDFcdWM3M2NcdWI4NWMgXHVjODE1XHVjNzU4XHVkNTU4XHVjNzkwXHViYTc0IFx1YmM0MFx1Yzc0MCBcdWM3NzQgXHVhY2E5XHVjNzkwIFx1YzU0OFx1YzVkMFx1YzExYyBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+PHA+MS4gMVx1Yzc3NCBcdWI0ZTRcdWM1YjQgXHVjNzg4XHViMjk0IFx1Y2U3OFx1Yzc0NCBcdWJjNDAgXHVhY2E5XHVjNzkwXHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC48YnIgXC8+XHJcbiZuYnNwOyZuYnNwOyZuYnNwOyAyLiBcdWJjNDBcdWM3NTggXHVjMmRjXHVjNzkxXHVjODEwXHVhY2ZjIFx1YjA1ZFx1YzgxMFx1Yzc0NCBcdWM4MWNcdWM2NzhcdWQ1NThcdWFjZTBcdWIyOTQgXHViYzQwIFx1YzU0OFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViYzQwIFx1YWNhOVx1Yzc5MFx1YjI5NCBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YmM0MCBcdWFjYTlcdWM3OTBcdWM2NDAgXHViOWNjXHViMDljJm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7IFx1YjJlNC4gKFx1YjNkOVwvXHVjMTFjXC9cdWIwYThcL1x1YmQ4MSBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMpIFx1YmM0MFx1Yzc1OCBcdWM1OTEgXHViMDVkXHVjODEwXHVjNzQwIFx1ZDU1YyBcdWFjMWNcdWM3NTggXHViYzQwIFx1YWNhOVx1Yzc5MFx1YzY0MCBcdWI5Y2NcdWIwOWNcdWIyZTRcdWFjZTAgXHVhYzAwXHVjODE1XHVkNTU4XHVjNWVjXHViM2M0Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7IFx1Yzg4Ylx1YjJlNC48XC9wPlxyXG48cD5cdWFkZjhcdWI5YWNcdWFjZTAgbWF4aW1hbCBzbmFrZVx1Yjc4MCwgXHVjNzA0XHVjNzU4IFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHViYzQwIFx1YjRlNCBcdWM5MTEsIFx1YmM0MFx1Yzc1OCBcdWM1OTFcdWNhYmQgXHViMDVkIFx1YzkxMSBcdWQ1NWMgXHVhZDcwXHViMzcwXHVjNWQwIDFcdWM3NDQgXHVjZDk0XHVhYzAwXHVjMmRjXHVkMGE4XHViMmU0XHViYTc0IFx1YjM1NCBcdWM3NzRcdWMwYzEgXHVjNzA0XHVjNzU4IFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWMyZGNcdWQwYTRcdWM5YzAgXHVjNTRhXHViMjk0IFx1YmM0MFx1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWJhNzQgXHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1YzVkMFx1YzExYyBcdWFjMDBcdWM3YTUgXHVjNjdjXHVjYWJkXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWFjZjNcdWM1ZDBcdWMxMWNcdWIyOTQgXHVkNTU4XHViMDk4XHVjNzU4IG1heGltYWwgc25ha2VcdWFjMDAgXHVjNzg4XHVhY2UwLCBcdWI0NTAgXHViYzg4XHVjOWY4XHVjNWQwXHViMjk0IFx1ZDU1YyBcdWFjMWNcdWM3NTggbWF4aW1hbCBzbmFrZVx1YjNjNCBcdWM3ODhcdWM5YzAgXHVjNTRhXHVhY2UwIFx1YzEzOCBcdWJjODhcdWM5ZjhcdWM1ZDBcdWIyOTQgXHVjMTM4XHVhYzFjXHVjNzU4IG1heGltYWwgc25ha2VcdWFjMDAgXHVjNzg4XHViMmU0LjxcL3A+XHJcbjxwPjxpbWcgd2lkdGg9XCI1NjdcIiBoZWlnaHQ9XCIxMzhcIiBhbHQ9XCJcIiBzcmM9XCJcL0p1ZGdlT25saW5lXC91cGxvYWRcLzIwMTAwN1wvc25rLnBuZ1wiIFwvPjxcL3A+XHJcbjxwPm4qbSBcdWFjYTlcdWM3OTBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODM4IFx1Yzc4OFx1Yzc0NCBcdWI1NGMsIFx1YmE4NyBcdWFjMWNcdWM3NTggbWF4aW1hbCBzbmFrZVx1YWMwMCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgbixtKDEmbHQ7PW4sbSZsdDs9MjAwKSBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgbisxXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMCBcdWFjYTlcdWM3OTBcdWM3NTggXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgbWF4aW1hbCBzbmFrZVx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+IiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjAzOSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlNuYWtlcyBvbiBhIFBsYW5lIiwiZGVzY3JpcHRpb24iOiI8cD5Bc3N1bWUgd2UgaGF2ZSBhbiBuJnRpbWVzO20gZ3JpZCBvZiBzcXVhcmVzLCBlYWNoIGZpbGxlZCB3aXRoIGVpdGhlciAwIG9yIDEuIEEgc25ha2UgaXMgYSBjb25uZWN0ZWQgc2VxdWVuY2Ugb2YgZ3JpZCBzcXVhcmVzIHdoaWNoIGhhcyB0aGUgZm9sbG93aW5nIHByb3BlcnRpZXM6PFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+RWFjaCBzbmFrZSBzcXVhcmUgaGFzIGEgMSBpbiBpdDxcL2xpPlxyXG5cdDxsaT5FYWNoIHNuYWtlIHNxdWFyZSB0b3VjaGVzIGV4YWN0bHkgdHdvIG90aGVyIHNuYWtlIHNxdWFyZXMgKG5vcnRoXC9zb3V0aFwvZWFzdFwvd2VzdCksIGV4Y2VwdCB0aGUgZmlyc3QgYW5kIGxhc3Qgc3F1YXJlIGluIHRoZSBzZXF1ZW5jZSAodGhlIGhlYWQgYW5kIHRhaWwgb2YgdGhlIHNuYWtlKTxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPkEgbWF4aW1hbCBzbmFrZSBpcyBvbmUgaW4gd2hpY2ggd2UgY2Fubm90IGFkZCBhIDEgdG8gZWl0aGVyIGVuZCB3aXRob3V0IGVpdGhlciBsZW5ndGhlbmluZyB0aGUgc25ha2UsIGNvbWJpbmluZyB0d28gc25ha2VzIHRvZ2V0aGVyLCBvciB2aW9sYXRpbmcgcnVsZSAyIGFib3ZlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgZXhhbXBsZXMgYmVsb3cgc2hvdyBncmlkcyB3aXRoIGFuZCB3aXRob3V0IG1heGltYWwgc25ha2VzIChhbGwgZW1wdHkgc3F1YXJlcyBoYXZlIDAmcnNxdW87cyBpbiB0aGVtKS4gTm90aWNlIHRoYXQgdGhlIHNlY29uZCBncmlkIGRvZXMgbm90IGhhdmUgYSBtYXhpbWFsIHNuYWtlIHNpbmNlIHlvdSBjYW4gYWRkIGEgMSBhdCB0aGUgZW5kIG9mIGVpdGhlciBzbmFrZSB0byBnZXQgYSBsYXJnZXIgc25ha2UuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvc25ha2VwbGEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTMxcHg7IHdpZHRoOjUxNXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkZvciB0aGlzIHByb2JsZW0sIHlvdSB3aWxsIGJlIGdpdmVuIGdyaWRzIGFuZCBtdXN0IGNvdW50IHRoZSBudW1iZXIgb2YgbWF4aW1hbCBzbmFrZXMgaW4gZWFjaC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPklucHV0IHdpbGwgY29uc2lzdCBvZiBtdWx0aXBsZSB0ZXN0IGNhc2VzLiBUaGUgXHVmYjAxcnN0IGxpbmUgb2YgZWFjaCB0ZXN0IGNhc2Ugd2lsbCBjb250YWluIHR3byBwb3NpdGl2ZSBpbnRlZ2VycyBuIG0gaW5kaWNhdGluZyB0aGUgbnVtYmVyIG9mIHJvd3MgYW5kIGNvbHVtbnMgaW4gdGhlIGdyaWQgKHRoZSBtYXhpbXVtIHZhbHVlIG9mIGVhY2ggd2lsbCBiZSAyMDApLiBUaGUgbmV4dCBuIGxpbmVzIHdpbGwgY29uc2lzdCBvZiBtIGNoYXJhY3RlcnMgKGVpdGhlciAmcnNxdW87MCZyc3F1bzsgb3IgJnJzcXVvOzEmcnNxdW87KSBzcGVjaWZ5aW5nIHRoZSBncmlkLiBUaGUgbGFzdCBjYXNlIGlzIGZvbGxvd2VkIGJ5IGEgbGluZSBjb250YWluaW5nIDAgMCB3aGljaCBpbmRpY2F0ZXMgZW5kLW9mLWlucHV0IGFuZCBzaG91bGQgbm90IGJlIHByb2Nlc3NlZC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCBhIHNpbmdsZSBsaW5lIGNvbnRhaW5pbmcgdGhlIG51bWJlciBvZiBtYXhpbWFsIHNuYWtlcyBpbiB0aGUgZ3JpZDxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==