← 返回题目列表

Codeforces · 1353/F

F. 高度降低

中文机器翻译题面 查看原题

您正在玩一款著名的三维世界沙盒游戏。世界地图可以表示为大小为 $$$n \times m$$$ 的矩阵,其中单元格 $$$(i, j)$$$ 的高度为 $$$a_{i, j}$$$。

您现在位于单元格 $$$(1, 1)$$$,并且想要进入单元格 $$$(n, m)$$$。您只能向下移动(从单元格 $$$(i, j)$$$ 到单元格 $$$(i + 1, j)$$$)或向右移动(从单元格 $$$(i, j)$$$ 到单元格 $$$(i, j + 1)$$$)。还有一个额外的限制:如果当前单元格的高度为 $$$x$$$,那么您只能移动到高度为 $$$x+1$$$ 的单元格。

在第一次移动之前,您可以执行多项操作。在一次操作期间,您可以将任何单元格的高度减少一。 IE。您选择某个单元格 $$$(i, j)$$$ 并分配(设置)$$$a_{i, j} := a_{i, j} - 1$$$。请注意,您可以使高度小于或等于零。另请注意,您可以减小单元格 $$$(1, 1)$$$ 的高度。

您的任务是找到为获得从单元格 $$$(1, 1)$$$ 到单元格 $$$(n, m)$$$ 的至少一条合适路径而必须执行的最少操作数。保证答案存在。

您必须回答 $$$t$$$ 独立测试用例。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。

测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 100$$$) — 世界地图中的行数和列数。接下来的 $$$n$$$ 行每行包含 $$$m$$$ 个整数,其中第 $$$i$$$ 行中的第 $$$j$$$ 个整数是 $$$a_{i, j}$$$ ($$$1 \le a_{i, j} \le 10^{15}$$$) — 单元格 $$$(i, j)$$$ 的高度。

保证所有测试用例的 $$$n$$$ 总和(以及 $$$m$$$ 总和)不超过 $$$100$$$ ($$$\sum n \le 100; \sum m \le 100$$$)。

输出

对于每个测试用例,打印答案 — 为获得从单元格 $$$(1, 1)$$$ 到单元格 $$$(n, m)$$$ 的至少一条合适路径而必须执行的最少操作数。保证答案存在。

示例

输入 #1

5
3 4
1 2 3 4
5 6 7 8
9 10 11 12
5 5
2 5 4 8 3
9 10 11 5 1
12 8 4 2 5
2 2 5 4 1
6 8 2 4 2
2 2
100 10
10 1
1 2
123456789876543 987654321234567
1 1
42

输出 #1

9
49
111
864197531358023
0