1520C.md (1243B)
1 Source: https://codeforces.com/problemset/problem/1520/C 2 3 C. Not Adjacent Matrix 4 5 time limit per test 6 7 4 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 We will consider the numbers $a$ and $b$ as adjacent if they differ by exactly one, that is, $|a-b|=1$. 22 23 We will consider cells of a square matrix $n \times n$ as adjacent if they have a common side, that is, for cell $(r, c)$ cells $(r, c-1)$, $(r, c+1)$, $(r-1, c)$ and $(r+1, c)$ are adjacent to it. 24 25 For a given number $n$, construct a square matrix $n \times n$ such that: 26 27 * Each integer from $1$ to $n^2$ occurs in this matrix exactly once; 28 * If $(r_1, c_1)$ and $(r_2, c_2)$ are adjacent cells, then the numbers written in them must not be adjacent. 29 30 Input 31 32 The first line contains one integer $t$ ($1 \le t \le 100$). Then $t$ test cases follow. 33 34 Each test case is characterized by one integer $n$ ($1 \le n \le 100$). 35 36 Output 37 38 For each test case, output: 39 40 * -1, if the required matrix does not exist; 41 * the required matrix, otherwise (any such matrix if many of them exist). 42 43 The matrix should be outputted as $n$ lines, where each line contains $n$ integers. 44 45 Example 46 47 Input 48 49 ``` 50 3 51 1 52 2 53 3 54 ``` 55 56 Output 57 58 ``` 59 1 60 -1 61 2 9 7 62 4 6 3 63 1 8 5 64 ```