题解 CF1333E 【Road to 1600】

· · 题解

首先发现 n \le 2 是没法做的。

然后 n = 3 可以暴力算一下，比如下面这种方案就是合法的：

那么，如果 n > 3，能不能转化一下变成 n = 3 的问题呢？

一种方法是使得外面的位置都不造成作用，只有最左上角的九格才发挥作用。

也就是我们只要确保两个棋子都能恰好将外面的绕完，然后进入最左上角的九宫格就行了，比如下面这样就是 n = 5 的构造方法：

\begin{matrix} \color{red} 1 \color{blue} + 16 & \color{red} 7 \color{blue} + 16 & \color{red} 9 \color{blue} + 16 & 7 \to & 8 \downarrow \\ \color{red} 3 \color{blue} + 16 & \color{red} 2 \color{blue} + 16 & \color{red} 5 \color{blue} + 16 & 6\uparrow & 9 \downarrow \\ \color{red} 4 \color{blue} + 16 & \color{red} 8 \color{blue} + 16 & \color{red} 6 \color{blue} + 16 & 5\uparrow & 10 \downarrow \\ 1 \to \ & 2 \to & 3 \to & 4\uparrow & 11 \downarrow \\ 16 \gets & 15 \gets & 14 \gets & 13 \gets & 12 \gets \end{matrix}

于是就是一个普及组的填数问题了。

代码仅供参考。

#include <bits/stdc++.h>
using namespace std;
const int N = 505;
int n, a[N][N];
int main()
{
    scanf("%d", &n);
    if(n <= 2) return puts("-1") && 0;
    int cnt = 0, outmax = n * n - 9;
    a[1][1] = 1 + outmax; a[1][2] = 7 + outmax; a[1][3] = 9 + outmax;
    a[2][1] = 3 + outmax; a[2][2] = 2 + outmax; a[2][3] = 5 + outmax;
    a[3][1] = 4 + outmax; a[3][2] = 8 + outmax; a[3][3] = 6 + outmax;
    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 >= 1; 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 >= 1; j--) a[i + 3][j] = ++cnt;
        }
    }
    for(int i = 1; i <= n; i++, puts(""))
        for(int j = 1; j <= n; j++) printf("%d ", a[i][j]); 
    return 0;
}