CF1621D The Winter Hike

圆形大陆是一个 $2n \times 2n$ 的网格。该网格的行从上到下编号为 $1$ 到 $2n$，列从左到右编号为 $1$ 到 $2n$。单元格 $(x, y)$ 表示第 $x$ 行第 $y$ 列的单元格，其中 $1 \leq x \leq 2n$ 且 $1 \leq y \leq 2n$。 在网格的左上角有 $n^2$ 个你的朋友。也就是说，在每个满足 $1 \leq x, y \leq n$ 的单元格 $(x, y)$ 中恰好有一个朋友。其他一些单元格被积雪覆盖。 你的朋友们想要到达网格的右下角。为此，在每个满足 $n+1 \leq x, y \leq 2n$ 的单元格 $(x, y)$ 中应恰好有一个朋友。每个朋友最终在右下角的哪个单元格并不重要。 你决定帮助你的朋友们到达网格的右下角。 为此，你可以给出如下类型的指令： - 你选择一行 $x$。该行的所有朋友都向该行的下一个单元格移动。即，位于 $(x, y)$ 的朋友（$1 \leq y < 2n$）会移动到 $(x, y+1)$，而位于 $(x, 2n)$ 的朋友会移动到 $(x, 1)$。 - 你选择一行 $x$。该行的所有朋友都向该行的上一个单元格移动。即，位于 $(x, y)$ 的朋友（$1 < y \leq 2n$）会移动到 $(x, y-1)$，而位于 $(x, 1)$ 的朋友会移动到 $(x, 2n)$。 - 你选择一列 $y$。该列的所有朋友都向该列的下一个单元格移动。即，位于 $(x, y)$ 的朋友（$1 \leq x < 2n$）会移动到 $(x+1, y)$，而位于 $(2n, y)$ 的朋友会移动到 $(1, y)$。 - 你选择一列 $y$。该列的所有朋友都向该列的上一个单元格移动。即，位于 $(x, y)$ 的朋友（$1 < x \leq 2n$）会移动到 $(x-1, y)$，而位于 $(1, y)$ 的朋友会移动到 $(2n, y)$。 请注意这些指令对边界上的朋友的影响。  上图为对第二列应用第三种操作的示例。彩色圆圈表示你的朋友，蓝色单元格为被积雪覆盖的单元格。 你可以任意多次给出上述指令，也可以混合使用不同类型的指令。如果在任何一次指令后，你的某个朋友位于被积雪覆盖的单元格，他就会生病。 为了拯救你的朋友们，你可以在给出第一条指令前移除某些单元格的积雪： - 你可以选择当前被积雪覆盖的单元格 $(x, y)$，并花费 $c_{x, y}$ 个金币移除该单元格的积雪。 你可以任意多次进行此操作。 你希望花费最少的金币，并给出一些指令，使得所有朋友都能到达网格的右下角，并且没有人生病。 请你计算你最少需要花费多少金币。

第一行包含一个整数 $t$（$1 \leq t \leq 100$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 250$）。 接下来的 $2n$ 行，每行包含 $2n$ 个整数 $c_{i, 1}, c_{i, 2}, \ldots, c_{i, 2n}$（$0 \leq c_{i, j} \leq 10^9$），表示移除每个单元格积雪的花费。如果 $c_{i, j} = 0$，则 $(i, j)$ 处没有积雪；否则，该单元格被积雪覆盖。 保证对于所有 $1 \leq i, j \leq n$，都有 $c_{i, j} = 0$。 保证所有测试用例中 $n$ 的总和不超过 $250$。

对于每个测试用例，输出一个整数，表示你最少需要花费的金币数。

在第一个测试用例中，你可以花费 $100$ 个金币移除单元格 $(2, 1)$ 和 $(2, 2)$ 的积雪。然后你可以给出如下指令： - 所有在第一列的朋友向上一个单元格移动。此后，你的朋友会在 $(2, 1)$。 - 所有在第二行的朋友向下一个单元格移动。此后，你的朋友会在 $(2, 2)$。 在第二个测试用例中，你可以花费 $22$ 个金币移除第 $3$ 列和第 $4$ 列的所有积雪。然后你可以给出如下指令： - 所有在第一行的朋友向下一个单元格移动。 - 所有在第一行的朋友向下一个单元格移动。 - 所有在第二行的朋友向下一个单元格移动。 - 所有在第二行的朋友向下一个单元格移动。 - 所有在第三列的朋友向下一个单元格移动。 - 所有在第三列的朋友向下一个单元格移动。 - 所有在第四列的朋友向下一个单元格移动。 - 所有在第四列的朋友向下一个单元格移动。 可以证明，没有朋友会生病，并且无法花费更少的金币。 由 ChatGPT 4.1 翻译