[NOIP 2015 提高组] 神奇的幻方

知识点

矩阵、构造、模拟

解题思路

先将1放在第一行中间。之后尝试向右上角移动并按模N处理边界；若该位置已填写，就改为向下移动一格。每次填写下一个整数。

正确性说明

右上位置的环绕规则分别覆盖顶边与右边；当位于右上角或右上位置已填时，向下规则与题目一致。由已完成前k-1步的状态按相同规则确定第k步，归纳可知整个矩阵就是题目指定构造。

易错点

N为奇数；坐标采用0下标，向上时用(r-1+N)%N避免负数；输出每行恰好N个数。

复杂度

时间O(N²)，空间O(N²)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;cin>>n;vector<vector<int>> a(n,vector<int>(n));int r=0,c=n/2;
    for(int k=1;k<=n*n;++k){a[r][c]=k;int nr=(r+n-1)%n,nc=(c+1)%n;
        if(a[nr][nc])r=(r+1)%n;else{r=nr;c=nc;}
    }
    for(auto &row:a){for(int j=0;j<n;++j)cout<<row[j]<<(j+1==n?'\n':' ');}
}