물 채우기
시간 제한2초메모리 제한128 MB
격자 형태의 지형 높이가 주어질 때, 경계에서 시작하는 우선순위 큐 방식으로 갇힐 수 있는 최대 물의 양을 계산합니다.
문제
N행 M열로 이루어진 물통이 있다. 각 칸에는 바닥 높이가 정해져 있으며, 서로 다른 칸의 높이는 다를 수 있다. 물통의 가장자리도 칸으로 이루어져 있고, 가장자리의 높이가 안쪽 칸보다 낮을 수도 있다.
이 물통에 충분히 물을 부은 뒤 더 이상 흘러나가지 않고 남아 있을 수 있는 물의 최대 총량을 구하시오. 물은 상하좌우로 인접한 칸을 통해 낮은 쪽으로 흘러나갈 수 있다.
입력
첫째 줄에 열의 수 M과 행의 수 N이 주어진다. (1 ≤ N, M ≤ 300)
다음 N개의 줄에는 각 행에 있는 M개의 자연수가 주어진다. 각 수는 해당 칸의 높이이며, 1,000,000,000을 넘지 않는다.
출력
물통에 남아 있을 수 있는 물의 최대 총량을 첫째 줄에 출력한다.
정답은 int 범위 안에 있으며, 0일 수도 있다.