The Winter Hike

题意翻译

你们班举行了一次冬游，冬游地点可以看作是一个 $2n\times 2n$ 的网格图。定义 $(x,y)$ 为该网格图中第 $x$ 行第 $y$ 列的格子。 除了你之外，班上正好有 $n^2$ 个同学。当你到的时候，所有同学都已经就位了，并且你发现，对于所有的 $1\leqslant x,y\leqslant n$，恰好有一个同学站在 $(x,y)$ 上。你向老师询问过后，得知他们准备玩一个游戏。具体地，老师每次会发出如下四种命令中的一种： - 所有第 $x$ 行上的同学都向右移动一格，如果会走出边界则回到第一列。即，对于 $1\leqslant y<2n$，站在 $(x,y)$ 上的同学要移动到 $(x,y+1)$，而站在 $(x,2n)$ 上的同学要移动到 $(x,1)$。 - 所有第 $x$ 行上的同学都向左移动一格，如果会走出边界则回到第 $2n$ 列。即，对于 $2\leqslant y\leqslant 2n$，站在 $(x,y)$ 上的同学要移动到 $(x,y-1)$，而站在 $(x,1)$ 上的同学要移动到 $(x,2n)$。 - 所有第 $y$ 列上的同学都向下移动一格，如果会走出边界则回到第一行。即，对于 $1\leqslant x<2n$，站在 $(x,y)$ 上的同学要移动到 $(x+1,y)$，而站在 $(2n,y)$ 上的同学要移动到 $(1,y)$。 - 所有第 $y$ 列上的同学都向上移动一格，如果会走出边界则回到第 $2n$ 行。即，对于 $2\leqslant x\leqslant 2n$，站在 $(x,y)$ 上的同学要移动到 $(x-1,y)$，而站在 $(1,y)$ 上的同学要移动到 $(2n,y)$。 当所有同学都站在了网格图的右下部分，且右下部分的每个格子上都恰好有一个同学，即，对于所有的 $n+1\leqslant x,y\leqslant 2n$，恰好有一个同学站在 $(x,y)$ 上时，游戏结束。 就在老师刚讲完游戏规则时，他突然意识到一个很严重的一点——在没有同学占领的部分格子上覆盖着雪。老师清楚地知道，如果在某次命令过后，有同学站在了一个覆盖着雪的格子上，他会因此而生病。于是，老师决定先推迟游戏，清理格子上的雪。在观察过后，老师发现，清理 $(i,j)$ 上的雪的花费为 $c_{i,j}$（$c_{i,j}=0$ 表示 $(i,j)$ 上没有雪）。 作为一个关心老师的学生，你希望老师能够通过尽量小的花费和若干次命令，使得整个游戏过程中不会有人生病。你只需要告诉老师最小花费是多少。 数据范围： - $t$ 组数据，$1\leqslant t\leqslant 100$。 - $1\leqslant n,\sum n\leqslant 250$。 - $0\leqslant c_{i,j}\leqslant 10^9$。 - 对于所有的 $1\leqslant i,j\leqslant n$，$c_{i,j}=0$。 Translated by Eason_AC 2022.1.4

题目描述

Circular land is an $ 2n \times 2n $ grid. Rows of this grid are numbered by integers from $ 1 $ to $ 2n $ from top to bottom and columns of this grid are numbered by integers from $ 1 $ to $ 2n $ from left to right. The cell $ (x, y) $ is the cell on the intersection of row $ x $ and column $ y $ for $ 1 \leq x \leq 2n $ and $ 1 \leq y \leq 2n $ . There are $ n^2 $ of your friends in the top left corner of the grid. That is, in each cell $ (x, y) $ with $ 1 \leq x, y \leq n $ there is exactly one friend. Some of the other cells are covered with snow. Your friends want to get to the bottom right corner of the grid. For this in each cell $ (x, y) $ with $ n+1 \leq x, y \leq 2n $ there should be exactly one friend. It doesn't matter in what cell each of friends will be. You have decided to help your friends to get to the bottom right corner of the grid. For this, you can give instructions of the following types: - You select a row $ x $ . All friends in this row should move to the next cell in this row. That is, friend from the cell $ (x, y) $ with $ 1 \leq y < 2n $ will move to the cell $ (x, y + 1) $ and friend from the cell $ (x, 2n) $ will move to the cell $ (x, 1) $ . - You select a row $ x $ . All friends in this row should move to the previous cell in this row. That is, friend from the cell $ (x, y) $ with $ 1 < y \leq 2n $ will move to the cell $ (x, y - 1) $ and friend from the cell $ (x, 1) $ will move to the cell $ (x, 2n) $ . - You select a column $ y $ . All friends in this column should move to the next cell in this column. That is, friend from the cell $ (x, y) $ with $ 1 \leq x < 2n $ will move to the cell $ (x + 1, y) $ and friend from the cell $ (2n, y) $ will move to the cell $ (1, y) $ . - You select a column $ y $ . All friends in this column should move to the previous cell in this column. That is, friend from the cell $ (x, y) $ with $ 1 < x \leq 2n $ will move to the cell $ (x - 1, y) $ and friend from the cell $ (1, y) $ will move to the cell $ (2n, y) $ . Note how friends on the grid border behave in these instructions. Example of applying the third operation to the second column. Here, colorful circles denote your friends and blue cells are covered with snow.You can give such instructions any number of times. You can give instructions of different types. If after any instruction one of your friends is in the cell covered with snow he becomes ill. In order to save your friends you can remove snow from some cells before giving the first instruction: - You can select the cell $ (x, y) $ that is covered with snow now and remove snow from this cell for $ c_{x, y} $ coins. You can do this operation any number of times. You want to spend the minimal number of coins and give some instructions to your friends. After this, all your friends should be in the bottom right corner of the grid and none of them should be ill. Please, find how many coins you will spend.

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \leq t \leq 100 $ ) — the number of test cases. The first line of each test case contains the single integer $ n $ ( $ 1 \leq n \leq 250 $ ). Each of the next $ 2n $ lines contains $ 2n $ integers $ c_{i, 1}, c_{i, 2}, \ldots, c_{i, 2n} $ ( $ 0 \leq c_{i, j} \leq 10^9 $ ) — costs of removing snow from cells. If $ c_{i, j} = 0 $ for some $ i, j $ than there is no snow in cell $ (i, j) $ . Otherwise, cell $ (i, j) $ is covered with snow. It is guaranteed that $ c_{i, j} = 0 $ for $ 1 \leq i, j \leq n $ . It is guaranteed that the sum of $ n $ over all test cases doesn't exceed $ 250 $ .

输出格式

For each test case output one integer — the minimal number of coins you should spend.

输入输出样例

输入样例 #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

说明

In the first test case you can remove snow from the cells $ (2, 1) $ and $ (2, 2) $ for $ 100 $ coins. Then you can give instructions - All friends in the first collum should move to the previous cell. After this, your friend will be in the cell $ (2, 1) $ . - All friends in the second row should move to the next cell. After this, your friend will be in the cell $ (2, 2) $ . In the second test case you can remove all snow from the columns $ 3 $ and $ 4 $ for $ 22 $ coins. Then you can give instructions - All friends in the first row should move to the next cell. - All friends in the first row should move to the next cell. - All friends in the second row should move to the next cell. - All friends in the second row should move to the next cell. - All friends in the third column should move to the next cell. - All friends in the third column should move to the next cell. - All friends in the fourth column should move to the next cell. - All friends in the fourth column should move to the next cell. It can be shown that none of the friends will become ill and that it is impossible to spend less coins.