1 条题解
-
0
好的,我已把思路补充到你预留的位置,保留了原代码不变。你可以整体复制下面这段覆盖原文:
# 题解 **题目类型**:构造奇数阶幻方(Magic Square) **核心算法**:缅甸法 / Siamese Method(仅适用于奇数 n) **思路与规则**: 1. **起点**:把数字 1 放在第一行的中间列(`x=1, y=n/2+1`)。 2. **默认移动**:下一个数字优先放到“右上”格(行减一、列加一,即 `(x-1, y+1)`)。 3. **越界环绕**:把棋盘看作环面 - 若越上界(`x==1`)且未越右界,则行绕到 `n`; - 若越右界(`y==n`)且未越上界,则列绕到 `1`; - 若同时在右上角(`x==1 && y==n`),按下一条“冲突规则”处理。 4. **冲突规则**:如果“右上”目标格已被占用(或右上角同时越界),则改为**正下**移动一步(`x++`,`y`不变)。 5. 重复 2–4,直到填满 \(n^2\) 个数。该方法保证每行、每列与两条对角线的和都为 \( \frac{n(n^2+1)}{2} \)。 **复杂度**:时间 \(O(n^2)\),空间 \(O(n^2)\)。 **注意**:本法仅适用于奇数阶;数组大小需覆盖到 `n×n`(当前代码 `ans[45][45]`,确保 `n≤44` 更稳妥)。 ```cpp #include <bits/stdc++.h> using namespace std; int ans[45][45]; int main() { int n; cin >> n; int x = 1, y = n / 2 + 1; ans[x][y] = 1; for (int i = 2; i <= n * n; i++) { if (x == 1 && y != n) x = n, y++; else if (x != 1 && y == n) x--, y = 1; else if (x == 1 && y == n) x++; else if (x != 1 && y != n) { if (!ans[x - 1][y + 1]) x--, y++; else x++; } ans[x][y] = i; } for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) cout << ans[i][j] << (j == n ? "\n" : " "); return 0; }
- 1
信息
- ID
- 3543
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者