시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB406525.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+biZ0aW1lczttIFx1YWNhOVx1Yzc5MFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4MzggXHVjNzg4XHVjNzQ0IFx1YjU0YywgXHViYTg3IFx1YWMxY1x1Yzc1OCBtYXhpbWFsIHNuYWtlXHVhYzAwIFx1Yzc4OFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgbiwgbSgxICZsZTsgbiwgbSAmbGU7IDIwMCkgXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIG4rMVx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgXHVhY2E5XHVjNzkwXHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBtYXhpbWFsIHNuYWtlXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjAzOSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlNuYWtlcyBvbiBhIFBsYW5lIiwiZGVzY3JpcHRpb24iOiI8cD5Bc3N1bWUgd2UgaGF2ZSBhbiBuJnRpbWVzO20gZ3JpZCBvZiBzcXVhcmVzLCBlYWNoIGZpbGxlZCB3aXRoIGVpdGhlciAwIG9yIDEuIEEgc25ha2UgaXMgYSBjb25uZWN0ZWQgc2VxdWVuY2Ugb2YgZ3JpZCBzcXVhcmVzIHdoaWNoIGhhcyB0aGUgZm9sbG93aW5nIHByb3BlcnRpZXM6PFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+RWFjaCBzbmFrZSBzcXVhcmUgaGFzIGEgMSBpbiBpdDxcL2xpPlxyXG5cdDxsaT5FYWNoIHNuYWtlIHNxdWFyZSB0b3VjaGVzIGV4YWN0bHkgdHdvIG90aGVyIHNuYWtlIHNxdWFyZXMgKG5vcnRoXC9zb3V0aFwvZWFzdFwvd2VzdCksIGV4Y2VwdCB0aGUgZmlyc3QgYW5kIGxhc3Qgc3F1YXJlIGluIHRoZSBzZXF1ZW5jZSAodGhlIGhlYWQgYW5kIHRhaWwgb2YgdGhlIHNuYWtlKTxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPkEgbWF4aW1hbCBzbmFrZSBpcyBvbmUgaW4gd2hpY2ggd2UgY2Fubm90IGFkZCBhIDEgdG8gZWl0aGVyIGVuZCB3aXRob3V0IGVpdGhlciBsZW5ndGhlbmluZyB0aGUgc25ha2UsIGNvbWJpbmluZyB0d28gc25ha2VzIHRvZ2V0aGVyLCBvciB2aW9sYXRpbmcgcnVsZSAyIGFib3ZlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgZXhhbXBsZXMgYmVsb3cgc2hvdyBncmlkcyB3aXRoIGFuZCB3aXRob3V0IG1heGltYWwgc25ha2VzIChhbGwgZW1wdHkgc3F1YXJlcyBoYXZlIDAmcnNxdW87cyBpbiB0aGVtKS4gTm90aWNlIHRoYXQgdGhlIHNlY29uZCBncmlkIGRvZXMgbm90IGhhdmUgYSBtYXhpbWFsIHNuYWtlIHNpbmNlIHlvdSBjYW4gYWRkIGEgMSBhdCB0aGUgZW5kIG9mIGVpdGhlciBzbmFrZSB0byBnZXQgYSBsYXJnZXIgc25ha2UuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvc25ha2VwbGEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTMxcHg7IHdpZHRoOjUxNXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkZvciB0aGlzIHByb2JsZW0sIHlvdSB3aWxsIGJlIGdpdmVuIGdyaWRzIGFuZCBtdXN0IGNvdW50IHRoZSBudW1iZXIgb2YgbWF4aW1hbCBzbmFrZXMgaW4gZWFjaC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPklucHV0IHdpbGwgY29uc2lzdCBvZiBtdWx0aXBsZSB0ZXN0IGNhc2VzLiBUaGUgXHVmYjAxcnN0IGxpbmUgb2YgZWFjaCB0ZXN0IGNhc2Ugd2lsbCBjb250YWluIHR3byBwb3NpdGl2ZSBpbnRlZ2VycyBuIG0gaW5kaWNhdGluZyB0aGUgbnVtYmVyIG9mIHJvd3MgYW5kIGNvbHVtbnMgaW4gdGhlIGdyaWQgKHRoZSBtYXhpbXVtIHZhbHVlIG9mIGVhY2ggd2lsbCBiZSAyMDApLiBUaGUgbmV4dCBuIGxpbmVzIHdpbGwgY29uc2lzdCBvZiBtIGNoYXJhY3RlcnMgKGVpdGhlciAmcnNxdW87MCZyc3F1bzsgb3IgJnJzcXVvOzEmcnNxdW87KSBzcGVjaWZ5aW5nIHRoZSBncmlkLiBUaGUgbGFzdCBjYXNlIGlzIGZvbGxvd2VkIGJ5IGEgbGluZSBjb250YWluaW5nIDAgMCB3aGljaCBpbmRpY2F0ZXMgZW5kLW9mLWlucHV0IGFuZCBzaG91bGQgbm90IGJlIHByb2Nlc3NlZC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCBhIHNpbmdsZSBsaW5lIGNvbnRhaW5pbmcgdGhlIG51bWJlciBvZiBtYXhpbWFsIHNuYWtlcyBpbiB0aGUgZ3JpZDxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > North America > East Central North America Regional > 2006 East Central Regional Contest G번

  • 문제를 다시 작성한 사람: kipa00