CF1065D Three Pieces

你遇到了一种新型的国际象棋谜题。你得到的棋盘不一定是 $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$），表示棋盘上每个格子上的数字。 保证所有 $A_{ij}$ 两两不同。

输出一行，包含两个整数，分别表示最优方案的步数和更换棋子的次数。

以下是第一个样例的步骤（起始棋子为马）： 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)$ 由 ChatGPT 4.1 翻译