Three Pieces

题意翻译

一个$N*N$的棋盘，每个棋盘上有一个序号，保证所有序号构成一个$1 - (N*N)$的排列。你要操控一个棋子按序号的顺序走完整个棋盘，即从1走到2……一直走到序号为N*N的节点。为了达成其中一次移动，你可能要走许多步。 你有三种棋子，车、马和象（行走规则参照国际象棋）。每走一步耗费1单位时间。你也可以在任意时刻耗费1单位时间更换棋子的种类（棋子的位置不变）。 求消耗的最短时间，以及在确保时间最短的情况下，棋子更换次数的最小值。

题目描述

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?

输入输出格式

输入格式

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.

输出格式

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

输入输出样例

输入样例 #1

3
1 9 3
8 6 7
4 2 5

输出样例 #1

12 1

说明

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) $