CF1333E Road to 1600

Egor 想要在著名的国际象棋网站 ChessForces 上达到 1600 分的等级分，他需要你的帮助！ 在你开始解题之前，Egor 想提醒你国际象棋棋子的走法。车可以沿着直线上下左右任意远地移动，并且可以随时停下。皇后可以沿着所有方向（垂直、水平和对角线）任意远地移动。你可以参考下图示例。  为了实现目标，Egor 需要研究如下问题： 有一个 $N \times N$ 的棋盘。棋盘上的每个格子都填有 $1$ 到 $N^2$ 之间的一个数字，且所有格子的数字互不相同。 一开始，有一个棋子站在编号为 $1$ 的格子上。注意，这个格子已经被视为访问过。之后每一步的移动规则如下： 1. 在所有尚未访问且棋子一步能到达的格子中，选择编号最小的那个格子前往。 2. 如果所有能一步到达的格子都已访问过，但仍有未访问的格子，则棋子会“传送”到编号最小的未访问格子。每次传送需要支付 $1$ vun。 3. 如果所有格子都已访问，则过程结束。 Egor 需要找到一个 $N \times N$ 的棋盘编号方案，使得在上述规则下，车支付的 vun 数量严格少于皇后。请你帮助他找到这样一个编号方案，或者告知不存在这样的方案。

输入仅一行，包含一个整数 $N$，表示棋盘的大小，$1 \le N \le 500$。

输出 $N$ 行，每行 $N$ 个数字，表示棋盘第 $i$ 行的编号。所有数字必须是 $1$ 到 $N \times N$ 的一个排列，每个数字恰好出现一次。 你的方案必须保证车支付的 vun 数量严格少于皇后。 如果无解，输出 $-1$。 如果有多种方案，输出任意一种均可。

对于 $1 \times 1$ 的棋盘，车和皇后都不会支付任何费用。 在第二个样例中，车的移动顺序为 $1 \to 3 \to 4 \to 6 \to 9 \to 5 \to 7 \to 13 \to 2 \to 8 \to 16 \to 11 \to 10 \to 12 \to 15 \to \textbf{(1 vun)} \to 14$。 皇后的移动顺序为 $1 \to 3 \to 4 \to 2 \to 5 \to 6 \to 9 \to 7 \to 13 \to 8 \to 11 \to 10 \to 12 \to 15 \to \textbf{(1 vun)} \to 14 \to \textbf{(1 vun)} \to 16$。 最终，车支付了 1 vun，皇后支付了 2 vuns。 由 ChatGPT 4.1 翻译