높이 지도

격자 높이대로 세운 기둥들이 이루는 입체에서 같은 평면에 이웃한 단위 정사각형을 한 면으로 묶어 면 개수를 셉니다.

보통7BFS정렬구간기하아직 제출이 없습니다시간 제한3초메모리 제한256 MB

문제

높이 지도는 양의 정수로 이루어진 2차원 행렬이고, 하나의 다면체를 나타낸다. 값이 VV인 칸에는 크기가 1×1×V1 \times 1 \times V인 직육면체 기둥이 1×11 \times 1 면을 바닥으로 하여 놓인다. 아래를 향한 1×11 \times 1 면이 모두 모여 바닥면 하나를 이루고, 위쪽과 옆쪽으로는 여러 개의 면이 생긴다.

예를 들어 값이 모두 2인 2×22 \times 2 행렬은 한 변의 길이가 2인 정육면체다. 값 하나가 1이면 같은 정육면체에서 귀퉁이 하나를 잘라낸 모양이 된다. 아래 그림이 두 경우를 함께 보여 준다.

이런 방식으로 나타낼 수 없는 다면체도 있지만, 나타낼 수 있는 다면체는 여럿이다. 다음은 다른 예시다.

높이 지도가 주어지면 그 다면체의 면이 몇 개인지 세어야 한다. 높이가 모두 정수이므로 다면체의 표면은 축에 평행한 단위 정사각형으로 나뉜다. 두 단위 정사각형이 같은 평면 위에 있고 바깥을 향하는 방향이 같으며 변 하나를 공유하면 두 정사각형은 같은 면에 속한다. 이 관계로 이어지는 단위 정사각형을 모두 모은 것이 면 하나다. 안쪽에 구멍이 있는 면도 하나로 센다. 예시에서 보듯 같은 평면 위의 서로 다른 두 면이 꼭짓점 하나나 변 하나, 또는 변의 일부를 공유하기도 한다.

입력

첫째 줄에 높이 지도의 행 개수 RR과 열 개수 CC가 주어진다 (1R,C1001 \le R, C \le 100). 다음 RR개 줄에는 각각 CC개의 정수가 주어진다. ii번째 줄의 jj번째 정수는 iijj열 칸의 값 Vi,jV_{i,j}다 (1Vi,j1091 \le V_{i,j} \le 10^9).

출력

높이 지도가 나타내는 다면체의 면 개수를 한 줄에 출력한다.