← 返回题目列表

Codeforces · 1065/D

D. 三件

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

你偶然发现了一种新的国际象棋谜题。给你的棋盘不一定是$$$8 \times 8$$$,但它仍然是$$$N \times N$$$。每个方块上都写有一些数字,所有数字都是从 $$$1$$$ 到 $$$N^2$$$ 并且所有数字都是成对不同的。第 $$$i$$$ 行中的第 $$$j$$$ 方格上写有数字 $$$A_{ij}$$$。

在你的国际象棋中,你只有三个棋子:马、象和车。首先,你将其中一个放在带有数字 $$$1$$$ 的方块上(你可以选择哪一个)。然后你想要到达方格$$$2$$$(可能在过程中穿过其他一些方格),然后方格$$$3$$$等等,直到到达方格$$$N^2$$$。在一个步骤中,您可以对当前棋子进行有效的移动,或者用其他棋子替换它。每个方格都可以被访问任意次数。

骑士可以移动到水平两格、垂直一格、或者垂直两格、水平一格的格子。主教沿对角线移动。车水平或垂直移动。移动的位置应与棋子当前所在的格子不同。

您想要最小化整个遍历的步骤数。在具有相同步数的所有路径中,您要选择棋子替换次数最少的路径。

满足所有条件应该采取什么路径?

输入

第一行包含一个整数 $$$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}$$$ 成对不同。

输出

唯一的一行应包含两个整数 - 最佳答案中的步数和其中的替换移动数。

示例

输入 #1

3
1 9 3
8 6 7
4 2 5

输出 #1

12 1

注意

以下是第一个示例的步骤(起始棋子是骑士):

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