Three Pieces
Contest: Educational Codeforces Round 52 (Rated for Div. 2)
Difficulty rating: 2200
Tags: dfs and similar, dp, shortest paths

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?

Input format:
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.

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

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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

Example input:
3
1 9 3
8 6 7
4 2 5

Example output:
12 1

Editorial:
There are a lot of different solutions for the problem. Most of them have the similar structure.
The first part is to find the shortest distance between the states $$$(x_1, y_1, p_1)$$$ and $$$(x_2, y_2, p_2)$$$, where $$$x$$$ and $$$y$$$ are the coordinates of the square and $$$p$$$ is the current piece. This can be done with 0-1 bfs, Floyd or Dijkstra. Just represent the triple as a single integer by transforming it to $$$(x \cdot n \cdot 3 + y \cdot 3 + p)$$$ and do everything on that graph.
The second part is to write some dp to go from $$$i$$$-th square with piece $$$p_1$$$ to $$$(i + 1)$$$-th square with piece $$$p_2$$$. The value of this $$$dp[n][3]$$$ is a pair (moves, replacements). It is easy to see that you can always choose the minimum of two such pairs while updating.
Overall complexity may vary. We believe, $$$O(n^4)$$$ is achievable. However, the particular solution I coded works in $$$O(n^6)$$$.