시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB66225716240.909%

문제

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

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

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

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

1에서 출발해서, 2, 3, ..., N2-1을 방문하고, N2까지 도착하는데 걸리는 시간의 최솟값을 구해보자. 최소 시간이 나오는 방법이 여러가지인 경우에는 말을 바꾸는 횟수를 최소로 하자.

입력

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

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

출력

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

예제 입력 1

3
1 9 3
8 6 7
4 2 5

예제 출력 1

12 1

나이트를 놓고 시작한다.

  1. (3, 2)로 이동한다. (2 방문)
  2. (1, 3)으로 이동한다. (3 방문)
  3. (3, 2)로 이동한다.
  4. 나이트를 룩으로 바꾼다.
  5. (3, 1)으로 이동한다. (4 방문)
  6. (3, 3)으로 이동한다. (5 방문)
  7. (3, 2)로 이동한다.
  8. (2, 2)로 이동한다. (6 방문)
  9. (2, 3)으로 이동한다. (7 방문)
  10. (2, 1)로 이동한다. (8 방문)
  11. (1, 1)로 이동한다.
  12. (1, 2)로 이동한다. (9 방문)

예제 입력 2

3
1 5 8
9 2 4
3 6 7

예제 출력 2

12 1

예제 입력 3

4
5 4 1 13
8 3 6 16
15 9 14 12
11 2 7 10

예제 출력 3

23 0

예제 입력 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

예제 출력 4

38 2

출처