[noip2015-提高] 神奇的幻方

GitHub跳转原题关系图返回列表

从第一行正中间的 1 开始，按四条互斥规则（右上出界回绕、右上角特判正下、被挡改下移）逐个落子，O(N²) 模拟填满幻方。

OJ: roj

题目 ID: 3628

难度:普及-

标签:模拟构造python

创建: 2026-10-02 11:19

更新: 2026-10-06 15:31

目录

  1. 题目描述
  2. 思路
  3. 参考代码

题目描述

幻方是由数字 1,2,⋯ ,N×N1,2,\cdots,N\times N 构成的 N×NN\times N 矩阵，每行、每列及两条对角线上的数字之和都相同。NN 为奇数时按如下方法构造：先把 11 写在第一行正中间，再从小到大依次填 K=2,⋯ ,N×NK=2,\cdots,N\times N。设 K−1K-1 位于 (r,c)(r,c)（行列下标从 00 计）：第一行非最后一列则填在最后一行、cc 右一列；最后一列非第一行则填在第一列、rr 上一行；第一行最后一列则填在正下方；否则右上方未填则填右上方，已填则填正下方。 输入一行一个正奇数 NN（1≤N≤391\leq N\leq39）；输出 NN 行、每行 NN 个整数，相邻两数用单空格隔开。样例输入 3，输出为三行：8 1 6、3 5 7、4 9 2。

思路

题面规则本身就是算法：从起点 (0,N/2)(0,N/2) 开始逐个数模拟，四条规则互斥且穷尽，每次 O(1)O(1) 判断落点，总共循环 N2N^2 次。输出本身就有 N2N^2 个数，所以模拟已是最优复杂度。矩阵初始化为 00，直接用它判断"右上方是否已填"即可。

参考代码

Python 版：

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 11:20
# update_at: 2026-10-02 11:20

import sys


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    square = [[0] * n for _ in range(n)]
    row, col = 0, n // 2  # 数字 1 的落点：第一行正中间

    for value in range(1, n * n + 1):
        square[row][col] = value
        # 四条规则按题面顺序判定：分支互斥，书写顺序即优先级。
        # 后两个分支隐含 row > 0 且 col < n-1，所以下标始终在棋盘内。
        if row == 0 and col != n - 1:
            row, col = n - 1, col + 1         # 上边非右上角 → 最后一行、右一列
        elif col == n - 1 and row != 0:
            row, col = row - 1, 0             # 右边非右上角 → 第一列、上一行
        elif row == 0 and col == n - 1:
            row += 1                          # 右上角 → 正下方
        elif square[row - 1][col + 1] == 0:   # 右上方为空 → 填右上方
            row, col = row - 1, col + 1
        else:                                 # 右上方已被占 → 填正下方
            row += 1

    print('\n'.join(' '.join(map(str, line)) for line in square))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 15:31
 * update_at: 2026-10-06 15:31
 */

// 按 NOIp2015 幻方的四条规则逐格模拟：向右上走、出界回绕、右上角特判正下、被挡改下移。

#include <cstdio>

typedef long long ll;

const int MAXN = 40; // N <= 39 且为奇数

ll n;              // 幻方边长
ll square[MAXN][MAXN]; // square[r][c] = 该格填的数，0 表示还没填

// 按题面规则从 (row,col) 求数字 K 的落点
void move_next(ll &row, ll &col) {
    if (row == 0 && col != n - 1) {        // 规则 1：第一行且非最后一列，回绕到最后一行、列右移
        row = n - 1;
        col = col + 1;
    } else if (col == n - 1 && row != 0) { // 规则 2：最后一列且非第一行，回绕到第一列、行上移
        row = row - 1;
        col = 0;
    } else if (row == 0 && col == n - 1) { // 规则 3：右上角，填正下方
        row = row + 1;
    } else if (square[row - 1][col + 1] == 0) { // 规则 4：右上方为空，填右上方
        row = row - 1;
        col = col + 1;
    } else {                               // 规则 4：右上方已被占，改填正下方
        row = row + 1;
    }
}

int main() {
    scanf("%lld", &n);
    ll row = 0;        // 数字 1 放在第一行正中间
    ll col = n / 2;
    for (ll k = 1; k <= n * n; ++k) {
        square[row][col] = k;
        move_next(row, col); // 求下一个数的落点；填到最后一个数时结果不再使用
    }
    for (ll r = 0; r < n; ++r) {
        for (ll c = 0; c < n; ++c) {
            printf("%lld%c", square[r][c], c == n - 1 ? '\n' : ' ');
        }
    }
    return 0;
}