← 返回题目列表

Codeforces · 1621/D

D. 冬季远足

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

圆形土地是一个 $$$2n \times 2n$$$ 网格。该网格的行从上到下用从 $$$1$$$ 到 $$$2n$$$ 的整数进行编号,该网格的列从左到右用从 $$$1$$$ 到 $$$2n$$$ 的整数进行编号。单元格 $$$(x, y)$$$ 是 $$$1 \leq x \leq 2n$$$ 和 $$$1 \leq y \leq 2n$$$ 的行 $$$x$$$ 和列 $$$y$$$ 的交集处的单元格。

网格左上角有 $$$n^2$$$ 位好友。也就是说,在 $$$(x, y)$$$ 和 $$$1 \leq x, y \leq n$$$ 的每个单元格中,只有一个朋友。其他一些牢房被雪覆盖。

你的朋友想要到达网格的右下角。为此,在 $$$(x, y)$$$ 和 $$$n+1 \leq x, y \leq 2n$$$ 的每个单元格中应该只有一个朋友。每个朋友在哪个牢房并不重要。

你决定帮助你的朋友到达网格的右下角。

为此,您可以发出以下类型的指令:

- 您选择一行$$$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$$$ 则单元格 $$$(i, j)$$$ 中没有雪。否则,单元格 $$$(i, j)$$$ 被雪覆盖。

对于$$$1 \leq i, j \leq n$$$,保证$$$c_{i, j} = 0$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$250$$$。

输出

对于每个测试用例,输出一个整数 - 您应该花费的最少硬币数量。

示例

输入 #1

4
1
0 8
1 99
2
0 0 0 0
0 0 0 0
9 9 2 2
9 9 9 9
2
0 0 4 2
0 0 2 4
4 2 4 2
2 4 2 4
4
0 0 0 0 0 0 0 2
0 0 0 0 0 0 2 0
0 0 0 0 0 2 0 0
0 0 0 0 2 0 0 0
0 0 0 2 2 0 2 2
0 0 2 0 1 6 2 1
0 2 0 0 2 4 7 4
2 0 0 0 2 0 1 6

输出 #1

100
22
14
42

注意

在第一个测试用例中,您可以使用 $$$100$$$ 硬币从 $$$(2, 1)$$$ 和 $$$(2, 2)$$$ 单元格中除雪。然后你就可以给出指示

- 第一个列中的所有朋友都应移动到上一个单元格。此后,您的朋友将位于单元格 $$$(2, 1)$$$ 中。
- 第二行的所有朋友都应该移动到下一个单元格。此后,您的朋友将位于单元格 $$$(2, 2)$$$ 中。

在第二个测试用例中,您可以从 $$$3$$$ 和 $$$4$$$ 列中移除所有雪,以获得 $$$22$$$ 硬币。然后你就可以给出指示

- 第一行的所有朋友都应该移动到下一个单元格。
- 第一行的所有朋友都应该移动到下一个单元格。
- 第二行的所有朋友都应该移动到下一个单元格。
- 第二行的所有朋友都应该移动到下一个单元格。
- 第三列中的所有朋友都应该移动到下一个单元格。
- 第三列中的所有朋友都应该移动到下一个单元格。
- 第四列中的所有朋友都应该移动到下一个单元格。
- 第四列中的所有朋友都应该移动到下一个单元格。

可以证明,没有一个朋友会生病,不可能少花点钱。