2023 年上海市大学生程序设计竞赛 - 一月赛

$\mathbf{\text{Because of the long statement, we will offer you a Chinese version of the statement.}}$

$\mathit{\text{Taiyi religion will always be prosperous.}}$

Komorebi is one of the chief apprentice of Taiyi religion, he specially loves studying tactical deployments, so he usually practices them with his younger martial brothers.

A tactical deployment can be regarded as a matrix with $n\times n$ size, everyone can stand in only one of the position of the deployment, and each position of the deployment can only contain no more than one person.

However, his younger martial brothers always forget the deployment, so Komorebi has to move them to correct place. For each operation, Komorebi can move one martial brother to adjacent empty position. Formally, if one of the martial brother is located at $(x,y)(1\le x,y\le n)$, there are four options that cost $1$ operation if Komorebi wants to move him:

1. If $x>1$ and $(x-1,y)$ is empty, Komorebi can move him to $(x-1,y)$.

2. If $y>1$ and $(x,y-1)$ is empty, Komorebi can move him to $(x,y-1)$.

3. If $x<n$ and $(x+1,y)$ is empty, Komorebi can move him to $(x+1,y)$.

4. If $y<n$ and $(x,y+1)$ is empty, Komorebi can move him to $(x,y+1)$.

One position is empty means that no person stands on it.

Besides, $\mathbf{\text{don’t forget that Komorebi is also one member in the deployment}}$, so he can stand on $\mathbf{\text{any}}$ empty position at $\mathbf{\text{any}}$ time, this costs $0$ operation, but if he wants to move after that, he should follow the rules above and also costs $1$ operation.

They need to practice $T$ tactical deployments, for each case, Komorebi will give you the ideal deployment and the current deployment, please help Komorebi to calculate the minimum number of operations to practice each of them.

以下是中文题面

$\mathit{\text{太乙长春。}}$

Komorebi是太乙教的首席大弟子，他十分精于演练阵法，也乐在其中，因此他经常与师弟们一起演练阵法。

一个阵法可以看作一个$n\times n$的矩阵，每个人都可以站在其中一个格子里，当然每个格子最多也只能站一个人。

然而，他的师弟们经常会忘记阵法，因此Komorebi就需要将他们移动到正确的位置上。每次操作他都可以将一名师弟移动到一个相邻的格子上。具体来说，如果一名师弟在坐标为$(x,y)$ $(1\le x,y\le n)$的格子上，那么Komorebi就可以花费一点操作点选择以下操作中的一项：

1. 如果 $x>1$ 且 $(x-1,y)$ 这个格子是空的，那么就可以将他移动到$(x-1,y)$.
2. 如果 $y>1$ 且 $(x,y-1)$ 这个格子是空的，那么就可以将他移动到$(x,y-1)$.
3. 如果 $x<n$ 且 $(x+1,y)$ 这个格子是空的，那么就可以将他移动到$(x+1,y)$.
4. 如果 $y<n$ 且 $(x,y+1)$ 这个格子是空的，那么就可以将他移动到$(x,y+1)$.

如果一个格子上没有人站着，那么我们就认为它是空的。

此外，Komorebi也是阵法中的一员，他可以选择在任意时刻站在任意位置上，这个操作不消耗操作点，但如果他后续还想要移动的话，那么就需要遵循上述操作，此时也会消耗一点操作点。

他们需要演练$T$个阵法，对于每个阵法，Komorebi会告诉你正确的阵法以及目前师弟们排出来的阵法，请你告诉他如果要正确地演练每一个阵法最少各需要多少操作点。