/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 350 点
問題文
縦 N 行 横 N 列のマスからなるグリッドがあります。ここで、N は 45 以下の奇数です。
上から i 行目、左から j 列目のマスをマス (i,j) と表します。
このグリッドに、以下の条件を満たすように高橋君と 1 から N^2-1 までの番号がついた N^2-1 個のパーツからなる 1 匹の龍を配置します。
- 高橋君はグリッドの中央、すなわちマス (\frac{N+1}{2},\frac{N+1}{2}) に配置しなければならない。
- 高橋君がいるマスを除く各マスには龍のパーツをちょうど 1 つ配置しなければならない。
- 2 \leq x \leq N^2-1 を満たす全ての整数 x について、龍のパーツ x はパーツ x-1 があるマスと辺で隣接するマスに配置しなければならない。
- マス (i,j) とマス (k,l) が辺で隣接するとは、|i-k|+|j-l|=1 であることを意味します。
条件を満たす配置方法を 1 つ出力してください。なお、条件を満たす配置は必ず存在します。
制約
- 3 \leq N \leq 45
- N は奇数である
入力
入力は以下の形式で標準入力から与えられる。
N
出力
N 行出力せよ。
X_{i,j} を、マス (i,j) に高橋君を配置するとき T、パーツ x を配置するとき x とし、i 行目には X_{i,1},\ldots,X_{i,N} を空白区切りで出力せよ。
入力例 1
5
出力例 1
1 2 3 4 5 16 17 18 19 6 15 24 T 20 7 14 23 22 21 8 13 12 11 10 9
この他、以下の出力も条件をすべて満たすため正解となります。
9 10 11 14 15 8 7 12 13 16 5 6 T 18 17 4 3 24 19 20 1 2 23 22 21
一方、以下の出力はそれぞれ不正解となります。
高橋君が中央にいない。
1 2 3 4 5 10 9 8 7 6 11 12 13 14 15 20 19 18 17 16 21 22 23 24 T
パーツ 23 とパーツ 24 のあるマスが辺で隣接していない。
1 2 3 4 5 10 9 8 7 6 11 12 24 22 23 14 13 T 21 20 15 16 17 18 19
Score : 350 points
Problem Statement
There is a grid with N rows and N columns, where N is an odd number at most 45.
Let (i,j) denote the cell at the i-th row from the top and j-th column from the left.
In this grid, you will place Takahashi and a dragon consisting of N^2-1 parts numbered 1 to N^2-1 in such a way that satisfies the following conditions:
- Takahashi must be placed at the center of the grid, that is, in cell (\frac{N+1}{2},\frac{N+1}{2}).
- Except for the cell where Takahashi is, exactly one dragon part must be placed in each cell.
- For every integer x satisfying 2 \leq x \leq N^2-1, the dragon part x must be placed in a cell adjacent by an edge to the cell containing part x-1.
- Cells (i,j) and (k,l) are said to be adjacent by an edge if and only if |i-k|+|j-l|=1.
Print one way to arrange the parts to satisfy the conditions. It is guaranteed that there is at least one arrangement that satisfies the conditions.
Constraints
- 3 \leq N \leq 45
- N is odd.
Input
The input is given from Standard Input in the following format:
N
Output
Print N lines.
The i-th line should contain X_{i,1},\ldots,X_{i,N} separated by spaces, where X_{i,j} is T when placing Takahashi in cell (i,j) and x when placing part x there.
Sample Input 1
5
Sample Output 1
1 2 3 4 5 16 17 18 19 6 15 24 T 20 7 14 23 22 21 8 13 12 11 10 9
The following output also satisfies all the conditions and is correct.
9 10 11 14 15 8 7 12 13 16 5 6 T 18 17 4 3 24 19 20 1 2 23 22 21
On the other hand, the following outputs are incorrect for the reasons given.
Takahashi is not at the center.
1 2 3 4 5 10 9 8 7 6 11 12 13 14 15 20 19 18 17 16 21 22 23 24 T
The cells containing parts 23 and 24 are not adjacent by an edge.
1 2 3 4 5 10 9 8 7 6 11 12 24 22 23 14 13 T 21 20 15 16 17 18 19