题目描述

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

现给定 N ，请构造 N*N 的幻方。

样例

N = 3 时，
输出：
8 1 6
3 5 7
4 9 2

算法

(模拟) $O(n^2)$

虽然按照题目中的提示那样做就好，但其实有一个简单好记的方法。
分下面几个步骤：

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

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

若K-1右上方没有填入过数字，则向K-1右上方填入K；

若K-1右上方已经填入过数字，则向K-1正下方填入K。

当然，这里说的右上方和正下方都是可能会跨出数组范围的，因此我在操作时用%把范围限制住了。

时间复杂度

$O(n^2)$

C++ 代码

#include <iostream>

const int N = 40;

int a[N][N];

int main()
{
    int n = 0;
    scanf("%d", &n);

    int row = 0;
    int col = (n-1)/2;

    a[row][col]=1;

    for (int i = 2; i <= n*n; i ++ )
    {
        row = (row - 1 + n) % n;
        col = (col + 1) % n;    //先将行和列定位到右上方↗   然后判断
        if (a[row][col] != 0)   //如果右上方已经填入数字  则还原并定位到正下方↓
        {
            row = ( row + 2 ) % n;
            col = ( col - 1 + n ) % n;  
        }
        a[row][col] = i;
    }

    for(int i = 0; i < n; i ++ )
    {
        for(int j = 0; j < n; j ++ )
            printf("%d ",a[i][j]);
        printf("\n");   
    }

    return 0;
}