시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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의 수를 출력하시오.

예제 입력

7 10
1111111110
0000000010
1100000011
1011110001
1010010001
1010010111
1110011100

예제 출력

1

힌트