시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 662 | 257 | 162 | 40.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개의 줄에 체스판에 적힌 수가 주어진다.
첫째 줄에 문제에 주어진 대로 방문하는데 필요한 시간의 최솟값과 말을 교체한 횟수를 출력한다.
3 1 9 3 8 6 7 4 2 5
12 1
나이트를 놓고 시작한다.
3 1 5 8 9 2 4 3 6 7
12 1
4 5 4 1 13 8 3 6 16 15 9 14 12 11 2 7 10
23 0
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
38 2