N\times M크기의 격자칸이 있다. 가장 왼쪽 위 칸을 (1, 1), 가장 오른쪽 아래 칸을 (N, M)이라고 하자.

격자칸의 제일 아래 행 바로 밑에는 물이 투과하지 못하는 바닥이 있다고 한다.

격자칸의 각 칸들은 막혀 있거나, 뚫려 있다. 막혀 있는 칸은 물이 투과하지 못한다.

한 열을 보면 막혀 있는 칸이 없거나, 막혀있는 칸들이 하나의 덩어리로 연속하여 나타난다.

인접한 막혀 있는 칸들 사이로 물이 투과하지 못한다.

한 열에 있는 덩어리가 가장 아래 행에 있는 칸을 포함할 때 이 덩어리를 바닥에 붙은 덩어리라고 부른다.

인접한 열에 있는 두 덩어리를 보았을 때, 두 덩어리가 같은 행에 있는 칸을 포함하면 두 덩어리는 붙어서 한 덩어리가 된다.

이렇게 붙은 세로 경계로도 물은 투과하지 못한다. 이렇게 붙는 과정은 연속한 열에 모두 적용된다.

이 격자칸에 위에서 물을 충분히 부었다고 하자.

각 열의 바닥에 붙은 덩어리들의 높이가 입력으로 주어졌을 때, 물이 고이는 칸들의 개수를 출력하는 프로그램을 작성하라.

쉬운 물채우기 timer 1s memory 256MB

쉬운 물채우기 1s 256MB