CF1333E Road to 1600 题解

题意：

埃戈尔希望在著名的国际象棋门户网站 ChessForces 上达到 1600 分的评分，他需要你的帮助！

在你开始解决问题之前，埃戈尔想提醒你国际象棋棋子的移动方式。国际象棋中的车沿直线方向上下左右移动，可以移动任意多的格子，并且可以随时停下来。皇后可以在所有垂直和对角线方向上任意距离移动。你可以参考下面的示例图。

为了达到目标，埃戈尔应该研究下一个主题：

有一个 \(N \times N\) 的棋盘。棋盘的每个格子里都有一个从 \(1\) 到 \(N^2\) 的数字，且所有格子中的数字都是不同的。

一开始，有一个棋子站在编号为 \(1\) 的格子上。注意，这个格子已经被视为访问过了。之后的每一步移动遵循以下规则：

在所有尚未访问过且棋子可以通过一步到达的格子中，它会前往编号最小的那个格子。

如果所有可到达的格子都已经访问过但仍有未访问的格子，那么棋子会传送到尚未访问的编号最小的格子。如果发生此步骤，棋子会支付 1 个 vun 的费用。

如果所有格子都已访问，过程停止。

埃戈尔应该找到一个 \(N \times N\) 的棋盘，使得车在这一轮编号中支付的 vun 严格少于皇后。帮助他找到这样的一个 \(N \times N\) 编号的棋盘，或者告诉他不存在这样的棋盘。

输入格式：

仅一行包含一个整数 \(N\) —— 棋盘的大小，\(1 \le N \le 500\)。

输出格式：

输出应包含 \(N\) 行。

在第 \(i\) 行输出 \(N\) 个数字——第 \(i\) 行的格子编号。所有编号从 \(1\) 到 \(N \times N\) 必须正好使用一次。

在你的棋盘上，车支付的 vun 必须严格少于皇后。

如果没有解决方案，打印 \(-1\)。

如果有多个解决方案，你可以输出其中任何一个。

这个题意有点难绷，总之我们需要设计陷阱来骗这个憨憨皇后 \(\large ♛\)。

注意到 \(n \le 2\) 必然无解，考虑 \(n > 2\) 的情况怎么构造。

\(n=3\) 的情况可以暴力构造出一个合法构造，如图所示（见参考文献1）：

由于我们只需要让车 \(\large ♜\) 的传送步数小于皇后 \(\large ♛\) 就好了

所以对于 \(n > 3\) 的情况我们可以让这俩憨憨兜圈子，兜到最后进入直接这个陷阱即可。 \[ \begin{array}{ccccc} 1+16 & 7+16 & 9+16 & 7 \rightarrow & 8 \downarrow \\[8pt]3+16 & 2+16 & 5+16 & 6 \uparrow & 9 \downarrow \\[8pt]4+16 & 8+16 & 6+16 & 5 \uparrow & 10 \downarrow \\[8pt]1 \rightarrow & 2 \rightarrow & 3 \rightarrow & 4 \uparrow & 11 \downarrow \\[8pt]16 \leftarrow & 15 \leftarrow & 14 \leftarrow & 13 \leftarrow & 12 \leftarrow \end{array} \] 时间复杂度 \(\mathcal{O}(n^2)\)

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)(555))

int a[N][N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n; cin >> n; if(n <= 2) return cout << "-1\n", 0;
    int cnt = 0, base = n * n - 9;
    a[1][1] = 1 + base; a[1][2] = 7 + base; a[1][3] = 9 + base;
    a[2][1] = 3 + base; a[2][2] = 2 + base; a[2][3] = 5 + base;
    a[3][1] = 4 + base; a[3][2] = 8 + base; a[3][3] = 6 + base;
    for(int i = 1; i <= n - 3; i++)
    {
        if(i & 1)
        {
            for(int j = 1; j <= i + 2; j++) a[i + 3][j] = ++cnt;
            a[i + 3][i + 3] = ++cnt;
            for(int j = i + 2; j > 0; j--) a[j][i + 3] = ++cnt;
        }else
        {
            for(int j = 1; j <= i + 2; j++) a[j][i + 3] = ++cnt;
            a[i + 3][i + 3] = ++cnt;
            for(int j = i + 2; j > 0; j--) a[i + 3][j] = ++cnt;
        }
    }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++) cout << a[i][j] << " \n"[j == n];
    return 0;
}