cho.sh

비 (Small)

섬의 높이 격자가 주어질 때, 비가 온 뒤 바다로 흘러나가지 못하고 고이는 물의 총량을 구한다.

보통5그래프BFS힙시뮬레이션아직 제출이 없습니다시간 제한5초메모리 제한512 MB

문제

바다에 섬이 하나 있다. 이 섬은 RR행 CC열의 행렬로 나타내며, 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

다른 예로 다음 섬을 보자.

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

폭우가 그치면 이 섬은 다음과 같이 된다.

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

맨 아랫줄에서 높이가 2인 칸은 바다와 변을 맞대고 있어 물이 고이지 않는다. 그 위의 높이 1인 세 칸에는 높이 2까지 물이 차므로 늘어난 높이의 합은 3이다.

섬의 높이 행렬이 주어질 때, 폭우가 그친 뒤 늘어난 높이의 합 ∑(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≤101 \le R \le 10
  • 1≤C≤101 \le C \le 10

출력

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