| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 168 | 73 | 57 | 50.000% |
$N \times N$ 크기의 격자가 주어진다. 이 격자의 각 칸에는 1ドル$이상 $N \times N$이하의 서로 다른 정수들이 1ドル$개씩 적혀있다. 어떤 격자의 1ドル$이 적힌 칸부터 시작해 상하좌우로 한 칸씩 움직이며 1ドル$부터 $N \times N$까지의 수를 차례대로 지나는 방법이 존재한다면 그 격자를 '좋은 격자'라고 하자. 주어진 격자에 다음의 시행을 원하는 만큼 할 수 있다.
시행을 통해 주어진 격자를 좋은 격자로 만드는 것이 가능한지 판별하고 가능하다면 좋은 격자로 만들기 위해 필요한 시행의 최소 횟수를 구하여라.
첫째 줄에 격자의 크기를 나타내는 정수인 $N$ 이 주어진다. $ (2 \leq N \leq 1\ 000)$
다음 $N$줄에는 정수가 $N$개씩 공백으로 구분되어 주어진다. $y+1$번째 줄의 $x$번째 수는 격자의 $y$행 $x$열에 적힌 수를 나타낸다. 이 수들은 1ドル$ 이상 $N \times N$ 이하의 서로 다른 정수임이 보장된다.
첫째 줄에 좋은 격자로 만들기 위한 시행의 최소 횟수를 출력한다. 만약 좋은 격자를 만드는 것이 불가능하다면 -1을 출력한다.
3 3 6 2 4 5 1 8 7 9
2
1행과 2행을 바꾼 후 1열과 2열을 바꾸면 좋은 격자가 된다.
$a$행과 $b$행을 교환한다는 것은 1ドル\leq i \leq N$인 모든 정수 $i$에 대해 $a$행 $i$열과 $b$행 $i$열의 수를 교환한다는 것이다. 비슷하게 $a$열과 $b$열을 교환한다는 것은 1ドル\leq i \leq N$인 모든 정수 $i$에 대해 $i$행 $a$열과 $i$행 $b$열의 수를 교환한다는 것이다.