뱀 찾기

0과 1로 이루어진 n x m 격자가 주어진다. 1이 들어 있는 칸들이 상하좌우로 이어져 하나의 모양을 만든다고 하자.

하나의 뱀은 1로 이루어진 연결된 칸들의 모임이다. 그 모임에서 양 끝을 제외한 모든 칸은 상하좌우로 인접한 같은 모임의 칸이 정확히 두 개여야 한다. 끝 칸은 뱀이 시작하거나 끝나는 칸이며, 한 칸만 있는 모임도 길이가 1인 뱀으로 본다.

뱀이 어느 끝에서든 더 길어질 수 있으면 극대 뱀이 아니다. 구체적으로, 끝 칸에 인접한 0 칸 하나를 1로 바꾸었을 때 그 새 칸이 그 끝 칸에만 닿아 뱀을 한 칸 더 늘릴 수 있다면 그 뱀은 극대가 아니다. 모든 끝에서 이런 확장이 불가능한 뱀을 극대 뱀이라고 한다.

격자가 주어졌을 때 극대 뱀의 개수를 구하시오.

첫째 줄에 정수 n, m(1 <= n, m <= 200)이 주어진다.

다음 n개 줄에는 격자의 정보가 주어진다. 각 줄은 0 또는 1로 이루어진 길이 m의 문자열이다.

첫째 줄에 극대 뱀의 개수를 출력하시오.