P16839 [GKS 2021 #A] Rabbit House

Barbara 去年在学校取得了非常好的成绩，因此她的父母决定送她一只宠物兔。她非常兴奋，为兔子建了一个房子，这个房子可以看作一个有 $R$ 行和 $C$ 列的二维网格。 兔子喜欢跳跃，因此 Barbara 在网格的若干个单元格上堆叠了几个箱子。每个箱子都是一个立方体，其尺寸正好与网格的一个单元格尺寸相匹配。 然而，Barbara 很快意识到，让兔子跳跃超过 $1$ 个箱子的高度可能会有危险，因此她决定通过调整房子来避免这种情况。对于每一对相邻的单元格，Barbara 希望它们的高度之差的绝对值不超过 $1$ 个箱子。如果两个单元格共享一条公共边，则认为它们是相邻的。 由于所有箱子都用强力胶粘住了，Barbara 无法移除任何初始已有的箱子，但她可以在它们上面添加箱子。她可以在任意多个单元格上添加任意数量的箱子（可以为零）。请帮助她确定使兔子的房子安全所需添加的最少箱子总数。

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。 每个测试用例的第一行包含两个整数 $R$ 和 $C$。 随后 $R$ 行，每行包含 $C$ 个整数。第 $i$ 行第 $j$ 列的整数 $G_{i,j}$ 表示网格中第 $i$ 行第 $j$ 列单元格上初始的箱子数量。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是使兔子的房子安全所需添加的最少箱子总数。

在样例 #1 中，每一对相邻单元格的高度差已经不超过 $1$ 个箱子，因此不需要添加任何箱子。 在样例 #2 中，最左边单元格与中间单元格的高度差为 $3$ 个箱子。为了解决这个问题，我们可以在中间单元格上添加 $2$ 个箱子。但随后中间单元格与最右边单元格的高度差变为 $2$ 个箱子，因此 Barbara 可以通过在最右边单元格上添加 $1$ 个箱子来解决。添加这 $3$ 个箱子后，安全条件得到满足。 在样例 #3 中，网格中间的单元格与其所有 $4$ 个相邻单元格的高度差均为 $2$ 个箱子。一种解决方案是向中间单元格的所有相邻单元格各添加恰好 $1$ 个箱子，这样任意一对相邻单元格的高度差都不超过 $1$ 个箱子。总共需要 $4$ 个箱子。 ### 限制条件 $1 \le T \le 100$。 对于所有 $i, j$，$0 \le G_{i,j} \le 2 \cdot 10^6$。 **测试集 1** $1 \le R, C \le 50$。 **测试集 2** $1 \le R, C \le 300$。 翻译由 DeepSeek V4 Pro 完成