Codeforces 1520C: Not Adjacent Matrix

Codeforces 1520C C++ 一解.

分析

只要求对 $n$ 阶方阵依次填充 $1,2,\cdots,n^2$, 一种常见的思考模式是依次将这个自然数序列填充到正确的位置. 显然对于本题一个较好的方案是间隔填充: 先从元素 $(0,0)$ (假定方阵左上角元素坐标为此, 其他类推) 开始每次间隔一格填充直至一行填充完毕, 再跳转到下一行间隔填充直至右下角元素 $(n-1,n-1)$, 接着顺序填充剩下的元素. 这样就能满足题意.

Codeforces 上编辑者博客中, MikeMirzayazov 用黑白棋盘举例, 先填充白格再填充黑格, 判定颜色依据为横纵坐标之和的奇偶性. 而以下的代码则直接将方阵拉长为长度为 $n$ 的一维数组, 直接根据下标的奇偶性填充数字, 效果类似. 当然以下的代码推出了每个坐标对应的数值的解析式, 并未利用到数组空间.

同时, 利用这样的填充方案, 显然可以得知当且仅当 $n=2$ 时找不到满足题意的方阵; 为方便编程, 这里将 $n=1$ 也做了特殊处理.

代码

#include <iostream>

using namespace std;

void solveAndPrint(int n)
{
    const int nn = n * n;

    if (n == 1)
    {
        cout << 1 << endl;
        return;
    }

    if (n == 2)
    {
        cout << -1 << endl;
        return;
    }

    if (n % 2)
    {
        for (int i = 0; i < nn; ++i)
        {
            if (i % 2)
            {
                cout << (nn + i) / 2 + 1 << ' ';
            }
            else
            {
                cout << i / 2 + 1 << ' ';
            }
            if ((i + 1) % n == 0)
            {
                cout << endl;
            }
        }
    }
    else
    {
        for (int i = 0; i < nn; ++i)
        {
            if (i % 2)
            {
                cout << (nn + i + 1) / 2 << ' ';
            }
            else
            {
                cout << i / 2 + 1 << ' ';
            }
            if ((i + 1) % n == 0)
            {
                cout << endl;
            }
        }
    }
}

int main()
{
    int t, n;

    cin >> t;
    for (int i = 0; i < t; ++i)
    {
        cin >> n;
        solveAndPrint(n);
    }

    return 0;
}