호수 만들기(Lake Making) timer 1s memory 128MB

박호수는 호수를 만들고자 한다. 박호수는 6 ft(피트) \times 6 ft크기의 정사각형 땅이 한 칸인 총 R행 \timesC열 크기의 부지를 구매하였다. 그리고 해당 부지의 각 칸 마다 평균 고도 elev_{R,C}를 측정하였다.

최근 근손실이 많이 일어난 박호수는 키우고 있는 소들에게 땅파기를 훈련시켰다. 소들은 왼쪽 상단 좌표가 R_S,C_S인 3 \times 3 정사각형 격자의 땅을 밟아 D_S인치만큼 고도를 낮춘다. (고도는 0 미만으로 내려가지 않는다)

그러나 낮은 고도에 있는 소는 나머지 무리가 합류할 때까지 발을 구르지 않는다. 따라서 모든 3 \times 3 정사각형 격자의 땅이 파지는 것은 아니다(또는 일부 부분이 다른 부분보다 덜 파질 수도 있음).

초기 고도 elev_{r,c}와 순서대로 정렬된 N개의 땅파기 명령, 그리고 호수의 최종 수위 E가 주어졌을 때 호수가 저장하는 물의 부피를 구하자.

답은 2,000,000,000을 초과하지 않음이 보장되며 그리고 호수의 가장자리에는 물이 흘러넘치지 않도록 방해물이 있다고 가정하자.

예를 들어 4 \times 6 크기의 부지를 호수로 변환한다고 하자.

초기 고도는 다음과 같다:

                      column
                  1  2  3  4  5  6
         row 1:  28 25 20 32 34 36
         row 2:  27 25 20 20 30 34
         row 3:  24 20 20 20 20 30
         row 4:  20 20 14 14 20 20

지도를 해석하면 오른쪽 상단 모서리에 고도 36인 작은 언덕이 올라가 있고, 왼쪽 상단 모서리에 고도 28인 작은 언덕이 있다. 4행 중간에는 약간의 움푹한 부분이 있다.

땅파기 명령 "1 4 4"를 수행한 후, 부지의 고도는 다음과 같다:

                  1  2  3  4  5  6
         row 1:  28 25 20 32 32 32
         row 2:  27 25 20 20 30 32
         row 3:  24 20 20 20 20 30
         row 4:  20 20 14 14 20 20

실제로 고도가 하강한 땅은 세 곳 뿐인데, 다른 여섯 칸에 위치한 소들은 더 높은 고도에 있는 소들이 그들이 있는 땅의 고도에 도달하기를 기다리고 있었으나 그러지 못했다.

땅파기 명령 "1 1 10"을 사용하여 왼쪽 상단 모서리를 밟은 후, 부지는 다음과 같이 보인다:

                  1  2  3  4  5  6
         row 1:  18 18 18 32 32 32
         row 2:  18 18 18 20 30 32
         row 3:  18 18 18 20 20 30
         row 4:  20 20 14 14 20 20

위와 같이 파여진 땅에 물을 채워 호수의 최종 고도가 22가 되게 한다면, 각 칸의 땅에 채워지는 물의 깊이는 다음과 같다:

                  1  2  3  4  5  6
         row 1:   4  4  4 -- -- --
         row 2:   4  4  4  2 -- --
         row 3:   4  4  4  2  2 --
         row 4:   2  2  8  8  2  2

이 때, 총 집계 깊이는 66이고, 총 물의 부피는 66 \times 6 ft x 6 ft = 66 \times 72 inch \times 72 inch = 342,144 inch^2 이다. (1피트는 12인치이다.)

이 계산을 자동화하는 프로그램을 작성해보자.