Changing the Sitting Arrangement

시간 제한8초메모리 제한1024 MB

요약
n×n 격자에 1부터 n^2까지 앉아 있는 학생들이 원래 격자에서 인접해 있었다면, 새 배치에서 맨해튼 거리가 ⌊n/2⌋ 이상이 되도록 자리를 다시 배치해 출력한다.
난이도

보통10점 중 6점

유형
구현, 수학, 행렬, 완전 탐색
정답자
아직 제출이 없습니다

문제

You are the teacher of a class of n2 pupils at an elementary school. Seats in the classroom are set up in a square shape of n rows (row 1 through row n) by n columns (column 1 through column n).

You are planning a change in the sitting arrangement. In order for your pupils to interact with many different pupils, you want to make those currently on adjacent seats have remote seats.

There is at least one sitting arrangement such that every pair of pupils currently on adjacent seats have seats with the Manhattan distance of no less than ⌊n / 2⌋ between them. Your task is to find such an arrangement. Here, ⌊x⌋ represents the largest integer less than or equal to x. The Manhattan distance of two seats are the sum of the absolute difference of their row numbers and that of their column numbers. Adjacent seats mean those with the Manhattan distance 1.

For example, in the first dataset of Sample Input (n = 4), pupils at the four adjacent seats of the pupil no. 10 are those numbered 6, 9, 11, and 14. In the Output for the Sample Input corresponding to this, their seats have Manhattan distances 3, 3, 2, and 3 from the seat of the pupil no. 10, all of which are ⌊ 4 / 2 ⌋ = 2 or greater. This condition also holds for all the other pupils.

입력

The input consists of multiple datasets, each in the format below. The number of datasets does not exceed 50.

n

a11 a12 ⋯ a1n

a21 a22 ⋯ a2n

 ⋮

a**n1 a**n2 ⋯ ann

Here, n is the number of rows and also columns of the seats in the classroom (2 ≤ n ≤ 50). The following n lines denote the current sitting arrangement. Each a**ij gives the ID number of the pupil currently sitting in the i-th row from the back and the j-th column from the left, as seen from the teacher's desk. a**ij's are integers 1 through n2, without duplicates.

The end of the input is indicated by a line consisting of a single zero.

출력

For each dataset, output a sitting arrangement satisfying the condition stated above in the same format as in the input. If there are two or more such arrangements, any of them will do.

예제1

  1. 예제 1

    입력
    4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
7
1 8 15 22 29 36 43
2 9 16 23 30 37 44
3 10 17 24 31 38 45
4 11 18 25 32 39 46
5 12 19 26 33 40 47
6 13 20 27 34 41 48
7 14 21 28 35 42 49
0
    예상 출력
    6 1 14 8
16 13 11 9
4 10 2 12
5 3 15 7
4 20 18 44 12 16 36
23 38 40 48 7 39 26
29 9 14 35 37 2 49
13 46 30 5 45 43 24
42 33 17 22 19 27 47
1 3 21 25 11 15 41
31 6 8 34 28 32 10