시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 59 31 28 53.846%

문제

1부터 N2까지의 수가 하나씩 채워져 있는 크기가 N×N인 배열이 있고, 이 배열의 모든 행, 열, 길이가 N인 대각선의 합이 모두 같을 때, 매직 스퀘어라고 한다.

크기가 3×3인 배열 A가 주어졌을 때, 이 배열을 매직 스퀘어로 변경하려고 한다. 한 칸에 있는 수 a를 b로 변경하는 비용은 |a - b| 이다. 예를 들어, 아래와 같은 경우를 살펴보자.

5 3 4
1 5 8
6 4 2

이 배열의 수를 아래와 같이 변경하면 매직 스퀘어가 되고, 비용은 |5 - 8| + |8 - 9| + |4 - 7| = 7 이다.

8 3 4
1 5 9
6 7 2

3×3 크기의 배열 A가 주어졌을 때, 이 배열을 매직 스퀘어로 변경하는 비용의 최솟값을 구해보자. 배열 A는 1부터 9까지의 수로만 채워져 있고, 매직 스퀘어로 변경한 배열도 1부터 9까지의 수로만 채워져 있어야 한다.

입력

총 세 개의 줄에 걸쳐서 배열 A의 원소가 주어진다.

출력

첫째 줄에 배열 A를 매직 스퀘어로 변경하는 비용의 최솟값을 출력한다.

예제 입력 1

4 9 2
3 5 7
8 1 5

예제 출력 1

1

가장 오른쪽 아랫칸의 수를 6으로 변경하면 매직 스퀘어가 되고, 비용은 |5 - 6| = 1이다.

예제 입력 2

4 8 2
4 5 7
6 1 6

예제 출력 2

4
4 9 2
3 5 7
8 1 6

으로 변경할 수 있고, 비용은 |8 - 9| + |4 - 3| + |6 - 8| = 4이다.

출처