cho.sh

비 (Large)

섬 격자가 주어질 때, 비가 온 뒤 물이 각 분지를 가장 낮은 주변 경계까지 채우며 생기는 전체 수위 상승량을 구한다.

보통6힙BFS행렬아직 제출이 없습니다시간 제한5초메모리 제한512 MB

문제

바다에 섬이 하나 있다. 섬은 RR행 CC열의 격자이고, ii번째 행 jj번째 열 칸의 높이는 H[i][j]H[i][j]이다. 다음은 3행 3열 섬의 예이다.

3 5 5
5 4 5
5 5 5

가끔 섬의 모든 칸에 폭우가 고르게 쏟아진다. 내리는 물의 양은 얼마든지 많다고 가정한다. 폭우가 그친 뒤 섬의 어떤 영역(변을 공유하며 이어진 칸 하나 이상)에는 물이 고일 수 있다. 물이 고이려면 영역 안의 칸이 영역 밖의 칸과 변을 공유하는 모든 곳에서 영역 밖의 칸이 더 높아야 한다. 꼭짓점만 맞닿은 경우는 변을 공유하는 것이 아니다. 섬을 둘러싼 바다는 높이가 0인 칸이 무한히 펼쳐진 격자로 본다. 이 조건을 만족하지 않는 영역의 물은 이웃한 영역 하나 이상으로 흘러가 결국 바다로 빠져나간다(어느 쪽으로 흐르는지는 상관없다). 바다의 높이는 변하지 않는다고 가정한다.

폭우가 그친 뒤 각 칸의 높이를 W[i][j]W[i][j]라고 하자. 위 예에서 처음 높이가 4인 칸은 자기보다 높은 칸하고만 맞닿아 있으므로 물이 고여 높이가 5가 된다. 그 뒤에는 더 높은 칸으로 둘러싸인 영역이 없으므로 물이 더 고이지 않는다. 다시 말하지만 물은 꼭짓점만 맞닿은 칸 사이로는 흐르지 못하고, 반드시 공유한 변을 따라 흐른다. 폭우가 그친 뒤 예시 섬의 높이는 다음과 같다.

3 5 5
5 5 5
5 5 5

섬의 높이가 주어질 때, 폭우가 그친 뒤 늘어난 높이의 합 ∑(W[i][j]−H[i][j])\sum (W[i][j] - H[i][j])를 구하시오.

입력

첫째 줄에 테스트 케이스의 수 TT가 주어진다. 이어서 TT개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫째 줄에는 섬의 행 수 RR과 열 수 CC가 주어진다. 다음 RR개의 줄에는 양의 정수가 CC개씩 주어진다. ii번째 줄의 jj번째 수는 ii번째 행 jj번째 열 칸의 높이 H[i][j]H[i][j]이다.

제한

  • 1≤T≤1001 \le T \le 100
  • 1≤H[i][j]≤10001 \le H[i][j] \le 1000
  • 1≤R≤501 \le R \le 50
  • 1≤C≤501 \le C \le 50

출력

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 폭우가 그친 뒤 늘어난 높이의 합이다.

힌트

예제 입력의 1번 케이스는 문제에서 설명한 섬이다.

2번 케이스의 섬은 폭우가 그친 뒤 다음과 같다.

5 5 5 1
5 2 2 5
5 2 5 5
5 2 5 8

3번 케이스의 섬은 폭우가 그친 뒤에도 변하지 않는다.