CF1065D.Three Pieces

You stumbled upon a new kind of chess puzzles. The chessboard you are given is not necesserily $8 \times 8$, but it still is $N \times N$. Each square has some number written on it, all the numbers are from $1$ to $N^2$ and all the numbers are pairwise distinct. The $j$-th square in the $i$-th row has a number $A_{ij}$ written on it.

In your chess set you have only three pieces: a knight, a bishop and a rook. At first, you put one of them on the square with the number $1$ (you can choose which one). Then you want to reach square $2$ (possibly passing through some other squares in process), then square $3$ and so on until you reach square $N^2$. In one step you are allowed to either make a valid move with the current piece or replace it with some other piece. Each square can be visited arbitrary number of times.

A knight can move to a square that is two squares away horizontally and one square vertically, or two squares vertically and one square horizontally. A bishop moves diagonally. A rook moves horizontally or vertically. The move should be performed to a different square from the one a piece is currently standing on.

You want to minimize the number of steps of the whole traversal. Among all the paths to have the same number of steps you want to choose the one with the lowest number of piece replacements.

What is the path you should take to satisfy all conditions?

你偶然发现了一种新型的国际象棋谜题。你所面对的棋盘不一定是 $8 \times 8$ 的，但它始终是 $N \times N$ 的。每个方格上都写有一个数字，所有数字均取自 $1$ 到 $N^2$，且两两互异。第 $i$ 行第 $j$ 列的方格上写的数字为 $A_{ij}$。

你的棋子套装中仅有三种棋子：马（knight）、象（bishop）和车（rook）。初始时，你将其中一种棋子放置在标有数字 $1$ 的方格上（可任选其一）。随后，你希望依次到达标有数字 $2$ 的方格（途中可经过其他方格），再到达标有数字 $3$ 的方格，依此类推，直至到达标有数字 $N^2$ 的方格。每一步操作允许你：(1) 用当前棋子执行一次合法移动，或 (2) 将当前棋子更换为另一种棋子。每个方格可被访问任意多次。

• 马可移动至横向相距两格、纵向相距一格，或纵向相距两格、横向相距一格的方格；
• 象沿对角线移动；
• 车沿水平或垂直方向移动。

每次移动必须到达一个与当前所在方格不同的方格。

你的目标是使整个遍历过程的总步数最小。在所有具有相同最少步数的路径中，你希望选择棋子更换次数最少的那一条路径。

你应当采取怎样的路径以满足上述所有条件？

The first line contains a single integer $N$ ($3 \le N \le 10$) — the size of the chessboard.

Each of the next $N$ lines contains $N$ integers $A_{i1}, A_{i2}, \dots, A_{iN}$ ($1 \le A_{ij} \le N^2$) — the numbers written on the squares of the $i$-th row of the board.

It is guaranteed that all $A_{ij}$ are pairwise distinct.

第一行包含一个整数 $N$（$3 \le N \le 10$）——棋盘的大小。

接下来的 $N$ 行中，每行包含 $N$ 个整数 $A_{i1}, A_{i2}, \dots, A_{iN}$（$1 \le A_{ij} \le N^2$）——表示棋盘第 $i$ 行各格子上所写的数字。

保证所有 $A_{ij}$ 两两互不相同。

The only line should contain two integers — the number of steps in the best answer and the number of replacement moves in it.

唯一的一行应包含两个整数——最优解中的步数以及其中的替换操作次数。

Here are the steps for the first example (the starting piece is a knight):

1. Move to $(3, 2)$
2. Move to $(1, 3)$
3. Move to $(3, 2)$
4. Replace the knight with a rook
5. Move to $(3, 1)$
6. Move to $(3, 3)$
7. Move to $(3, 2)$
8. Move to $(2, 2)$
9. Move to $(2, 3)$
10. Move to $(2, 1)$
11. Move to $(1, 1)$
12. Move to $(1, 2)$

第一个示例的步骤如下（起始棋子为马）：

1. 移动到 $(3, 2)$
2. 移动到 $(1, 3)$
3. 移动到 $(3, 2)$
4. 将马替换为车
5. 移动到 $(3, 1)$
6. 移动到 $(3, 3)$
7. 移动到 $(3, 2)$
8. 移动到 $(2, 2)$
9. 移动到 $(2, 3)$
10. 移动到 $(2, 1)$
11. 移动到 $(1, 1)$
12. 移动到 $(1, 2)$