103353: [Atcoder]ABC335 D - Loong and Takahashi
Description
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
Input
Output
问题描述
有一个$N$行$N$列的网格，其中$N$是一个最多为45的奇数。
让$(i,j)$表示从顶部数第$i$行，从左数第$j$列的单元格。
在这个网格中，你需要放置Takahashi和一个由$N^2-1$个部分组成的大龙，编号为1到$N^2-1$，以满足以下条件：
- Takahashi必须放在网格的中心，即在单元格$(\frac{N+1}{2},\frac{N+1}{2})$中。
- 除Takahashi所在的单元格外，每个单元格中必须放置一个大龙部分。
- 对于满足$2 \leq x \leq N^2-1$的每个整数$x$，大龙部分$x$必须放在包含部分$x-1$的单元格相邻的单元格中。
- 如果且仅当$|i-k|+|j-l|=1$，则说单元格$(i,j)$和$(k,l)$相邻。
打印一种满足条件的布局方式。保证存在至少一种满足条件的布局方式。
约束
- $3 \leq N \leq 45$
- $N$是奇数。
输入
输入从标准输入按以下格式给出：
$N$
输出
打印$N$行。
第$i$行应该包含$X_{i,1},\ldots,X_{i,N}$，由空格分隔，其中$X_{i,j}$为T时在单元格$(i,j)$中放置Takahashi，为$x$时在该单元格中放置部分$x$。
样例输入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
另一方面，以下输出由于给出的原因是错误的。
Takahashi不在中心。
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