← 返回题目列表

AtCoder · abc335_d

G. 龙和高桥

中文机器翻译题面 查看原题

分数: 350 点

问题陈述

有一个网格 N 行和 N 列,其中 N 最多为奇数 45.

让 (i,j) 表示位于 i从顶部开始的第行和 j左起第 列。

在这个网格中,你将放置高桥和一条由以下组成的龙 N^2-1 零件编号 1 to N^2-1 以满足以下条件:

  • 高桥必须放置在网格的中心,即单元格中 (\frac{N+1}{2},\frac{N+1}{2}).
  • 除了高桥所在的单元格外,每个单元格中必须放置恰好一个龙部件。
  • 对于每个整数 x 满意 2 \leq x \leq N^2-1,龙部分 x 必须放置在与包含部件的单元格相邻的单元格中 x-1.
    • 细胞 (i,j) 和 (k,l) 被称为由边相邻当且仅当 |i-k|+|j-l|=1.

打印一种排列零件以满足条件的方法。保证至少有一种排列满足条件。

约束

  • 3 \leq N \leq 45
  • N 是奇数。

输入

输入由标准输入按以下格式给出:

N

输出

打印 N 行。
的 i- 第行应包含 X_{i,1},\ldots,X_{i,N} 用空格分隔,其中 X_{i,j} is T 将高桥放入牢房时 (i,j) 和 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

另一方面,由于给出的原因,以下输出是不正确的。

高桥不在中心。

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