cho.sh

아틀란티스에 내리는 비 (라지)

높이 격자와 하루 침식 한도가 주어질 때 수위 흐름에 따른 침식으로 전체 지도가 0이 될 때까지 걸리는 일수를 구합니다.

어려움8힙그래프시뮬레이션아직 제출이 없습니다시간 제한5초메모리 제한512 MB

문제

아틀란티스 섬에 비가 내린다. 이 비는 섬의 땅을 남김없이 깎아낸다. 대피를 준비하려면 그때가 언제인지부터 알아야 한다.

아틀란티스의 지도가 있다. 지도는 정사각형 칸으로 이루어진 격자이고, 각 칸에는 그 칸의 땅 높이가 해수면 기준 미터 단위로 적혀 있다. 지도 밖의 칸은 모두 높이가 0이다. 높이가 0인 칸은 물이고, 높이가 0보다 큰 칸은 땅이다. 높이가 0보다 낮은 칸은 없다.

물은 땅 위에 고인다. 어떤 칸의 땅 높이에 그 위에 고인 물의 깊이를 더한 값을 그 칸의 수위라 하고, 칸 XX의 수위를 L(X)L(X)로 쓴다. 지도 밖 칸의 수위는 항상 0이다.

두 칸이 변을 맞대고 있고 목표 칸의 수위가 출발 칸의 수위보다 낮거나 같으면, 물은 출발 칸에서 목표 칸으로 흐른다.

비는 아주 빠르게 내린다. 어떤 칸의 빗물이 흘러갈 곳이 없으면 흘러갈 칸이 생길 때까지 그 칸에 물이 고인다. 지도 밖의 칸은 물을 얼마든지 받아들인다. 예를 들어 다음 지도는 금방 물이 찬다.

5 9 9 9 9 9
0 8 9 0 2 5
3 9 9 9 9 9

수위는 다음과 같이 된다.

5 9 9 9 9 9
0 8 9 5 5 5
3 9 9 9 9 9

땅 한가운데에 있는 0은 물이지만 지도 바깥과 이어져 있지 않아서 물이 고이기만 한다. 반면 왼쪽 가장자리에 있는 0은 지도 바깥과 이어져 있어서, 옆 칸 8의 물이 그 칸을 지나 지도 밖으로 흘러 나간다.

물이 흐르는 방향은 수위가 정한다. 한 칸에서 물이 흘러갈 수 있는 칸이 여럿이면 물은 수위가 가장 낮은 칸으로 흐른다. 수위가 가장 낮은 칸이 여럿이어도 결과는 달라지지 않는다.

이제 침식이 시작된다. 매일 각 칸은 물이 흘러 나가는 정도만큼 높이가 줄어든다. 물이 SS에서 TT로 흐르면 SS의 높이는 min⁡(L(S)−L(T), M)\min(L(S) - L(T),\ M)만큼 줄어든다. 침식은 그날 하루가 끝나는 순간에 모두 한꺼번에 일어난다. 예를 들어 M=5M = 5이면 위 지도는 다음과 같이 깎인다.

0 4 4 4 4 4
0 3 5 0 2 0
0 4 4 4 4 4

하루치 침식이 끝나면 남는 물은 흘러 나간다. 이웃 칸보다 수위가 높은 칸은 두 수위가 같아질 때까지 물을 잃고, 첫날과 같은 방식으로 다시 물이 고인다. 첫날이 지난 뒤 이 지도의 수위는 다음과 같다.

0 4 4 4 4 4
0 3 5 2 2 0
0 4 4 4 4 4

하루 더 침식이 일어나면 지도는 다음과 같아진다.

0 0 0 0 0 0
0 0 2 0 0 0
0 0 0 0 0 0

아틀란티스 사람들은 서둘러 섬을 빠져나가야 한다. 모든 칸의 높이가 0이 될 때까지 며칠이 걸리는지 구하여라.

입력

첫 줄에 테스트 케이스의 개수 TT가 주어진다. 이어서 TT개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 세 정수 HH, WW, MM이 공백으로 구분되어 주어진다. 앞의 두 수는 지도의 크기이고, 마지막 수는 한 칸이 하루에 깎일 수 있는 높이의 최댓값이다. 이어서 HH개의 줄에 각각 WW개의 정수가 공백으로 구분되어 주어진다. jj번째 줄의 ii번째 정수는 칸 (i,j)(i, j)의 높이다.

제한

  • 1≤T≤401 \le T \le 40
  • 1≤H,W≤201 \le H, W \le 20
  • 1≤M≤10151 \le M \le 10^{15}
  • 모든 높이는 00 이상 101510^{15} 이하이다.

출력

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. xx는 1부터 시작하는 테스트 케이스 번호이고, yy는 섬 전체가 깎여 사라지기까지 걸리는 날수이다.

설명

M=3M = 3이고 지도가 다음과 같은 경우를 보자.

3 8 10 11 10 8
7 5 2 12 8 8
6 9 11 9 8 4

처음 수위는 다음과 같다.

3 8 10 11 10 8
7 7 7 12 8 8
6 9 11 9 8 4

하루가 지나면 섬의 높이는 다음과 같다.

0 5 7 8 7 5
4 5 2 9 8 5
3 6 8 6 5 1

이틀이 지나면 다음과 같다.

0 2 4 5 4 2
1 4 2 6 5 2
0 3 5 3 2 0

사흘이 지나면 다음과 같다.

0 0 1 2 1 0
0 1 2 3 2 0
0 0 2 0 0 0

나흘이 지나면 아틀란티스의 사정은 절박해진다.

0 0 0 0 0 0
0 0 1 0 0 0
0 0 0 0 0 0

닷새째에 마지막 한 칸이 깎여 사라진다. 아틀란티스는 닷새를 버텼다. 도시를 흑설탕으로 짓지 말았어야 했다.