Description

亚特兰蒂斯岛上正下着大雨，雨水将会把所有的陆地侵蚀殆尽。为了组织撤离，你需要知道这一切将在多久之后发生。

你有一张亚特兰蒂斯的地图。地图是一个正方形网格，每个格子包含该格子高于海平面的高度（单位为米）。地图外的所有格子的高度都为 $0$；所有高度为 $0$ 的格子为水域，高度大于 $0$ 的格子为陆地。不存在高度小于 $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$ 处的水可以通过它流向外部。

水的流动方向由水位高度决定。如果某个源格子有多个可能的目标格子可流向，则水会流向水位最低的那个格子（如果有多个最低的格子，选择哪个都无所谓）。

接下来开始侵蚀。每天，每个格子的高度会根据水的流动情况减少。如果水从 $S$ 流向 $T$，则 $S$ 的高度减少 $\min(\text{WaterLevel}(S) - \text{WaterLevel}(T), M)$。所有侵蚀在一天结束时同时发生。例如，若 $M=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$ 需要多少天。

Input Format

输入的第一行是测试用例数 $T$。接下来有 $T$ 个测试用例。每个测试用例第一行为三个用空格分隔的整数：$H$、$W$ 和 $M$。前两个数表示地图的尺寸，第三个数表示每个格子一天最多被侵蚀的高度。接下来有 $H$ 行，每行包含 $W$ 个用空格分隔的整数，第 $j$ 行第 $i$ 个整数表示 $(i, j)$ 位置的格子的高度。

Output Format

对于每个测试用例，输出一行，格式为 "Case #$x$: $y$"，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是岛屿全部被侵蚀为 $0$ 所需的天数。

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

Case #1: 3
Case #2: 5

Hint

在第二个样例中，水位如下：

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

第五天最后一个格子被侵蚀殆尽。亚特兰蒂斯坚持了五天；他们大概不该用红糖建城。

数据范围

• $1 \leq T \leq 40$。

小数据集（7 分，测试点 1 - 可见）

• $1 \leq H, W \leq 10$。
• $1 \leq M \leq 100$。
• $0 \leq \text{所有高度} \leq 100$。
• 时间限制：30 3 秒。

大数据集（23 分，测试点 2 - 隐藏）

• $1 \leq H, W \leq 20$。
• $1 \leq M \leq 10^{15}$。
• $0 \leq \text{所有高度} \leq 10^{15}$。
• 时间限制：60 6 秒。

由 ChatGPT 4.1 翻译