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

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

按奇阶幻方规则从首行中间开始填数，优先走右上格，已占用则向下。

OJ: luogu

题目 ID: P2615

难度:普及-

标签:模拟矩阵python

日期: 2026-07-15 18:48

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. Pythonic 写法
  6. 复杂度
  7. 总结

题意

给出奇数 N，按题面规则构造一个 N * N 幻方，并输出矩阵。

规则可以概括为：从第一行中间放 1，之后每次尝试把下一个数放到上一个数的右上方；如果右上方越界就循环到另一边；如果右上方已经填过，就放到上一个数的正下方。

思路

用二维列表 square 保存矩阵，空位置用 0 表示。

当前位置是 (row, col)。填入当前数字后，先计算右上方：

text
next_row = (row - 1) % n
next_col = (col + 1) % n

取模可以自然处理“从第一行跳到最后一行”“从最后一列跳到第一列”。

如果 square[next_row][next_col] == 0，说明右上方没有填过，就移动过去。否则移动到当前格子的正下方。

Python 知识

  • /home/rainboy/mycode/hugo-blog/content/program_language/python/oj_input_output_cheatsheet.md：二维矩阵可以用列表推导式创建。
  • /home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md：print(*line) 可以把一行矩阵用空格输出。
  • % n 可以把越界行列绕回矩阵另一侧。
  • [[0 for _ in range(n)] for _ in range(n)] 能创建互不共享的二维列表。

代码

python
n = int(input())

square = [[0 for _ in range(n)] for _ in range(n)]

row = 0
col = n // 2

for value in range(1, n * n + 1):
    square[row][col] = value

    next_row = (row - 1) % n
    next_col = (col + 1) % n

    if square[next_row][next_col] == 0:
        row, col = next_row, next_col
    else:
        row += 1

for line in square:
    print(*line)
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-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

#include <bits/stdc++.h>
using namespace std;

int a[40][40]; // 幻方矩阵
int n;

int main() {
    cin >> n;
    int row = 1, col = (n + 1) / 2; // 第一行中间放 1
    for (int v = 1; v <= n * n; v++) {
        a[row][col] = v;
        // 计算右上方坐标（取模实现循环）
        int nr = (row - 1 + n - 1) % n + 1; // 行 -1，循环到最下面
        int nc = col % n + 1;               // 列 +1，循环到最左边
        if (a[nr][nc] != 0) {               // 右上方已被占用
            row++;                          // 放到正下方
        } else {
            row = nr;
            col = nc;
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            cout << a[i][j] << " ";
        cout << "\n";
    }
    return 0;
}

Pythonic 写法

幻方模拟精简：

python
n = int(input())
g = [[0] * n for _ in range(n)]
r, c = 0, n // 2
for v in range(1, n * n + 1):
    g[r][c] = v
    nr, nc = (r - 1) % n, (c + 1) % n
    r, c = (nr, nc) if g[nr][nc] == 0 else (r + 1, c)
for row in g:
    print(*row)

复杂度

一共填 n^2 个数，时间复杂度是 O(n2)O(n^2)，矩阵空间复杂度是 O(n2)O(n^2)。

总结

这题的难点是把题面的四种边界情况统一成“右上取模”。再加一个“目标格已占用则向下”的判断，代码会比逐条分支更短。