체스판 여행 1

시간 제한2초메모리 제한512 MB

요약

1부터 N^2까지의 수가 적힌 N×N 판에서 나이트, 비숍, 룩을 이용해 1, 2, ..., N^2 순서로 칸을 방문할 때 필요한 최소 시간(이동 또는 기물 교체 1초)을 구한다.

난이도: 어려움10점 중 8점
유형: BFS, 최단 경로, 그래프, 동적 계획법
정답자: 아직 제출이 없습니다

문제

크기가 $N\times N$ 인 체스판이 있고, 체스판의 각 칸에는 1부터 $N^2$ 까지의 정수가 한 번씩 적혀 있다. 지학이는 이 체스판을 이용해서 재미있는 게임을 해보려고 한다.

지학이가 가지고 있는 말은 나이트, 비숍, 룩이다. 가장 먼저 1이 적혀 있는 칸에 말 하나를 놓는다. 그다음, 1, 2, ..., $N^2$ 순서로 이동시키려고 한다.

먼저 1에 나이트, 비숍, 룩 중 하나를 놓는다. 그다음, 말을 이동시켜서 2가 적힌 칸으로 이동시킨다. 1에서 2로 이동시킬 때, 다른 수가 적힌 칸을 방문할 수도 있다. 그다음에는 3이 적힌 칸으로 이동시키고, ..., $N^2$ 이 적힌 칸으로 이동시킨다. 같은 칸을 여러 번 방문하는 것도 가능하다.

지학이가 1초 동안 할 수 있는 행동은 체스판 위에 놓인 말을 이동시키거나, 다른 말로 바꾸는 것이다.

1에서 출발해서 2, 3, ..., $N^2-1$ 을 방문하고 $N^2$ 까지 도착하는 데 걸리는 시간의 최솟값을 구해보자.

입력

첫째 줄에 체스판의 크기 $N(3 \le N \le 10)$ 이 주어진다.

둘째 줄부터 $N$ 개의 줄에 체스판에 적힌 수가 주어진다.

출력

첫째 줄에 문제에 주어진 대로 방문하는 데 필요한 시간의 최솟값을 출력한다.

예제4

예제 1
입력
```
3
1 9 3
8 6 7
4 2 5
```
예상 출력
```
12
```
예제 2
입력
```
3
1 5 8
9 2 4
3 6 7
```
예상 출력
```
12
```

예제 3

입력

예상 출력

예제 4

입력

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

예상 출력