| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 79 | 3 | 2 | 11.765% |
A knight’s tour on a rectangular board of n rows and m columns of squares (traditionally 8-by-8) is a labelling of the squares by integers 1 through n*m so that label (n+1) is a knight’s move from label n. That is, 2 squares horizontally and 1 square vertically or 1 square horizontally and 2 squares vertically. The image below shows an 8-by-8 knight’s tour.
A knight’s tour (on a square board) is (semi-)magical if the sum of the values in each row and column is the same (for the 8-by-8 case the sum would be 260). For this problem, you will be given a sequence of semi-magical 8-by-8 knight’s tours with many of the labels removed (see the image below). Write a program to fill in the missing labels so the knight’s tour is semi-magical.
The first line of input contains a single decimal integer P, (1 ≤ P ≤ 10000), which is the number of data sets that follow.
Each data set should be processed identically and independently. Each data set consists of a multiple lines of input. The first line of each data set contains the data set number, K. This line is followed by 8 lines each containing 8 integers separated by spaces giving the labels for the corresponding row. If the label value is -1, the label has been removed and your program is to find the correct value to put in that place.
For each data set there are 9 lines of output. The first output line contains the data set number, K. The following 8 lines should contain 8 integers each, separated by spaces, filling in the removed values to give a complete semi-magical knight’s tour which includes the positive labels from the input. There may be multiple correct answers. Your result will be graded correct if it is a semi-magical knight’s tour and the positive labels from the input are in the same square in your answer.
1 1 1 48 -1 -1 33 -1 63 18 30 51 -1 3 -1 -1 -1 -1 -1 -1 -1 -1 15 -1 -1 -1 -1 -1 -1 45 -1 -1 36 -1 -1 -1 25 -1 9 -1 21 60 -1 -1 -1 -1 24 57 12 -1 -1 6 -1 -1 39 -1 -1 -1 54 -1 42 -1 -1 -1 -1 -1
1 1 48 31 50 33 16 63 18 30 51 46 3 62 19 14 35 47 2 49 32 15 34 17 64 52 29 4 45 20 61 36 13 5 44 25 56 9 40 21 60 28 53 8 41 24 57 12 37 43 6 55 26 39 10 59 22 54 27 42 7 58 23 38 11