물채우기

$N \times M$ 크기의 격자칸이 있다. 가장 왼쪽 위 칸을 $(1, 1)$, 가장 오른쪽 아래 칸을 $(N, M)$이라고 하자. 격자칸의 가장 아래 행 바로 밑에는 물이 투과하지 못하는 바닥이 있다.

격자칸의 각 칸은 막혀 있거나 뚫려 있다. 막힌 칸은 물이 투과하지 못한다. 한 열을 보면 막힌 칸이 없거나, 막힌 칸들이 하나의 덩어리로 연속해서 나타난다. 인접한 막힌 칸들 사이로도 물은 투과하지 못한다. 한 열에서 가장 아래 행의 칸을 포함하는 덩어리를 바닥에 붙은 덩어리라고 부른다. 바닥에 붙지 않은 덩어리는 공중에 뜬 덩어리라고 부른다.

인접한 열에 있는 두 덩어리가 같은 행의 칸을 포함하면 두 덩어리는 붙어서 하나의 덩어리가 된다. 이렇게 붙은 세로 경계도 물은 투과하지 못한다. 이 과정은 연속한 열 모두에 적용된다. 아래 그림의 두 번째와 세 번째 열처럼 바닥에 붙은 덩어리와 공중에 뜬 덩어리가 붙는 경우는 주어지지 않는다. 즉, 인접한 열의 덩어리가 붙는 경우는 둘 다 바닥에 붙었거나 둘 다 공중에 뜬 경우뿐이다. 또 아래 그림의 다섯 번째와 여섯 번째 열처럼 두 덩어리가 꼭짓점 하나에서만 만나는 경우도 주어지지 않는다.

예를 들어 아래 그림은 $8 \times 12$ 크기의 격자칸이다. 이 격자칸의 첫 번째 열은 6번째 칸부터 8번째 칸까지 막혀 있고, 두 번째 열은 막힌 칸이 없으며, 세 번째 열은 5번째 칸부터 8번째 칸까지 막혀 있다.

이 격자칸에 위에서 물을 충분히 부었다고 하자. 1번으로 표시된 칸에는 물이 고인다. 2번으로 표시된 칸도 마찬가지다. 3번과 4번으로 표시된 칸에도 물이 고인다. 이 부분은 주의가 필요하다. 이 문제에서는 공기가 없다고 생각하므로 4번 부분도 3번 부분과 같은 높이까지 물이 찬다. (공기가 모든 것을 투과한다고 생각해도 결과는 같다.) 5번 부분은 공중에 뜬 덩어리 위에 물이 고인 경우다. 6번 부분과 같은 경우에는 물이 고이지 않는다.

칸들의 배치가 주어졌을 때, 물을 충분히 부었을 때 물이 고이는 칸의 개수를 출력하는 프로그램을 작성하라.