题目描述

幻方是一种很神奇的矩阵：它由数字 1,2,3,…, N*N 构成，且每行、每列及两条对角线上的数字之和都相同。

当N为奇数时，我们可以通过以下方法构建一个幻方：  

首先将 1 写在第一行的中间。 

之后，按如下方式从小到大依次填写每个数K(K= 2,3,…, N*N )： 

1. 若 (K−1) 在第一行但不在最后一列，则将K填在最后一行，(K−1) 所在列的右一列； 
2. 若 (K−1) 在最后一列但不在第一行，则将K填在第一列，(K−1) 所在行的上一行； 
3. 若 (K−1) 在第一行最后一列，则将K填在 (K−1) 的正下方； 
4. 若 (K−1) 既不在第一行，也不在最后一列，如果 (K−1) 的右上方还未填数，则将K填在(K−1)的右上方，否则将K填在 (K−1) 的正下方。

现给定N，请按上述方法构造 N*N 的幻方。

样例

输入样例：
3

输出样例：
8 1 6
3 5 7
4 9 2

这貌似是一道暴力模拟的题…
跟着题目说的操作就行了.
注意二位数组下标变化的规律.

时间复杂度 $O(n^2)$

(有$n^2$个数,时间复杂度自然是$n^2$级别的)

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int N,k[50][50];
void ma(int num)
{
    for(int i=1;i<=N;i++)//跟着题目说的操作即可
        for(int j=1;j<=N;j++){
            if(k[i][j]==num-1){
                if(i==1&&j!=N)
                    k[N][j+1]=num;
                if(i!=1&&j==N)
                    k[i-1][1]=num;
                if(i==1&&j==N)
                    k[i+1][j]=num;
                if(i!=1&&j!=N){
                    if(!k[i-1][j+1])
                        k[i-1][j+1]=num;
                    else
                        k[i+1][j]=num;
                }
            }
            else
                continue;
        }
}
int main()
{
    //freopen("magic.in","r",stdin);
    //freopen("magic.out","w",stdout);
    scanf("%d",&N);
    k[1][(N+1)/2]=1;//先填一
    for(int i=2;i<=N*N;i++)//再分别处理2-n^2
        ma(i);  
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            printf("%d ",k[i][j]);
        }
        printf("\n");
    }
    return 0;
}