Chessboard Tour 1

Time limit2sMemory limit512 MB

Summary

On an N by N board holding distinct numbers, find the fewest seconds (each a single piece move or a piece swap) to travel through squares 1, 2, ..., N^2 in order using a knight, bishop, and rook.

Level: Hard8 of 10
Topics: BFS, Shortest path, Graph, Dynamic programming
Solved: No attempts yet

Problem

There is an $N\times N$ chessboard, and each square contains a distinct integer from 1 to $N^2$ . Jihak wants to play an interesting game using this board.

The pieces Jihak has are a knight, a bishop, and a rook. First, he places one piece on the square containing 1. Then he wants to move it through 1, 2, ..., $N^2$ in that order.

He first places one of the knight, bishop, and rook on 1. Then he moves the piece to the square containing 2. When moving from 1 to 2, the piece may visit squares containing other numbers. Next he moves it to the square containing 3, ..., and to the square containing $N^2$ . Visiting the same square multiple times is also allowed.

In one second, Jihak can either move the piece on the board or change it to a different piece.

Find the minimum time needed to start at 1, visit 2, 3, ..., $N^2-1$ , and arrive at $N^2$ .

Input

The first line gives the size of the chessboard, $N$ ( $3 \le N \le 10$ ).

From the second line, $N$ lines give the numbers written on the chessboard.

Output

On the first line, print the minimum time needed for the visit described in the problem.

Examples4

Example 1
Input
```
3
1 9 3
8 6 7
4 2 5
```
Expected output
```
12
```
Example 2
Input
```
3
1 5 8
9 2 4
3 6 7
```
Expected output
```
12
```

Example 3

Input

Expected output

Example 4

Input

5
21 14 2 3 12
19 8 16 18 7
9 17 10 15 4
24 5 1 23 11
25 13 22 6 20

Expected output