使用二维数组模拟填数过程,通过方向数组控制走向,当遇到边界或已填过的格子时改变方向。
OJ: roj
题目 ID: 5047
难度:入门
标签:模拟二维数组
创建: 2026-10-08 20:57
更新: 2026-10-08 20:57
形式化题目
给定一个正整数
最终按行从上到下、从左到右的顺序输出该矩阵。每行输出
正解
思路
这是一个典型的二维数组模拟题。我们需要一个二维数组来保存填入的数字,并模拟依次填入每个数字的过程。
为了实现填数,我们需要维护当前所在的坐标
我们可以使用“方向数组”来简化代码,设 dx 和 dy 分别表示四个方向在
- 向下:
dx = 1, dy = 0 - 向左:
dx = 0, dy = -1 - 向上:
dx = -1, dy = 0 - 向右:
dx = 0, dy = 1
我们从数字
- 如果
越界(超出 的范围),或者 这个格子已经被填过了(非 ),说明当前方向不能继续走,此时需要顺时针改变方向(方向索引 d = (d + 1) % 4),重新计算下一步。 - 否则,方向不变。
- 接着更新
,准备填下一个数字。
输出时,只需遍历整个二维数组即可。注意控制单空格分隔、行末没有多余的空格,且末尾恰有一个换行。
本题数据由自制脚本生成。
代码
#!/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-08 20:40
# update_at: 2026-10-08 20:40
import sys
# 四个方向的增量,按「下、左、上、右」顺时针循环,与 C++ 版一致
DX = (1, 0, -1, 0)
DY = (0, -1, 0, 1)
def spiral(n: int) -> list[list[int]]:
"""从右上角起笔,按「下、左、上、右」螺旋填入 1..n*n,返回 n×n 方阵。"""
a = [[0] * n for _ in range(n)]
x, y, d = 0, n - 1, 0 # 起点为右上角 (0, n-1),方向 0 即先向下
for v in range(1, n * n + 1):
a[x][y] = v
nx, ny = x + DX[d], y + DY[d] # 先看后走:越界或已填过就顺时针转一次
if not (0 <= nx < n and 0 <= ny < n) or a[nx][ny]:
d = (d + 1) % 4
nx, ny = x + DX[d], y + DY[d]
x, y = nx, ny
return a
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n = next(data)
sys.stdout.write(''.join(' '.join(map(str, row)) + '\n' for row in spiral(n)))
if __name__ == '__main__':
solve()/**
* 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-08 20:40
* update_at: 2026-10-08 20:40
*/
#include <iostream>
using namespace std;
typedef long long ll;
const int MAXN = 25;
// 方阵,a[i][j] 表示第 i 行第 j 列填入的数字,0 表示还没填过
int a[MAXN][MAXN];
// 四个方向的增量,按「下、左、上、右」顺时针循环:
// 0=下(dx=1,dy=0) 1=左(0,-1) 2=上(-1,0) 3=右(0,1)
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};
// 从右上角起笔,按「下、左、上、右」螺旋填入 1..n*n
void solve() {
ll n;
if (!(cin >> n)) return;
ll x = 0, y = n - 1; // 起点:第 0 行、第 n-1 列(右上角)
ll dir = 0; // 当前方向下标,初值 0 即先向下
for (ll v = 1; v <= n * n; ++v) {
a[x][y] = v;
// 先看后走:下一步越界或已填过,就顺时针转一次方向
ll nx = x + dx[dir];
ll ny = y + dy[dir];
if (nx < 0 || nx >= n || ny < 0 || ny >= n || a[nx][ny] != 0) {
dir = (dir + 1) % 4;
nx = x + dx[dir];
ny = y + dy[dir];
}
x = nx;
y = ny;
}
for (ll i = 0; i < n; ++i) {
for (ll j = 0; j < n; ++j) {
cout << a[i][j] << (j == n - 1 ? "" : " "); // 行末不留多余空格
}
cout << "\n";
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
return 0;
}复杂度
- 时间复杂度:
。矩阵中共有 个格子,每个格子刚好被填入一次并被遍历输出一次,每次判断和移动(转向至多发生 次)只需要常数时间。 - 空间复杂度:
。需要一个 的二维数组来存储所有的数字。 ,可以直接开全局数组 a[25][25],空间极小。
总结
蛇形的精确定义与反推
蛇形填数在不同题目的语境中有多种互不相同的常见定义(例如:右上逆时针、左下顺时针、或“S 形”对角线/行间回字)。做此类题目必须以数据为准而非凭印象。
我们可以通过真实数据,逐点反推数字
:值 在 ,转向序列 。 :值 在 ,转向序列 。 :值 在 ,转向序列 。 :值 在 ,转向序列 。
由此确认了:起点必须是右上角 下→左→上→右 循环。
各核心要素的承重实验
一旦搞错方向或起笔,就会引发数据错误。以下是通过反事实验证得出的各要素改动后果:
| 改动 | 结果 | 典型失败点 |
|---|---|---|
逆时针转弯 (d+1)%4 → (d+3)%4 |
9 组 FAIL | 0 1(应为 4 1) |
起点改左上角 (0,0) |
9 组 FAIL | 1 0 |
| 去掉「已填过」转向条件 | 8 组 FAIL | 7 8 9 |
| 扰动方向表 | 9 组 FAIL | 4 3 |
| 分隔符改双空格 | 全 9 组 FAIL(非 |
— |
| 行末留多余空格 | 全 10 组 FAIL | — |
| 文件末尾多一个空行 | 全 10 组 FAIL | — |
这些实验证明了:转弯旋向、起点角、已填判定、分隔符 均为程序的关键承重点。
反事实实验的选点教训
反事实实验必须选择“真正承重”的变量去修改,否则会得出错误结论。 例如,如果我们保持当前代码的起点是右上角不变,试图把初始方向“从下改为向右(先右后下)”,程序的输出并不会改变。这是因为一上来朝右走就会立刻越界,程序会立刻执行转向操作转回向下。 这使得“方向表前两项的先后”变得不可观测。这很容易让人误以为“方向表怎么写都行”,但实际上真正承重的是方向的旋向以及起点角,它们一旦被修改,立刻会导致大面积失败。
细节与边界
- 静态全局数组:在 C++ 中,直接使用全局二维数组
int a[MAXN][MAXN],不仅符合项目惯例,在较小时也避免了 std::vector的额外开销。 - 边界
:最小输入为 ,输出单独的 1加上换行。不需要发生任何转向。 - 输出格式:要求极其严格的单空格分隔、行尾无多余空格、末尾恰好一个
\n、无多余空行。在 Python 中,通过先组装成完整字符串再sys.stdout.write输出,能精确控制尾部换行;C++ 中可使用(j == n - 1 ? "" : " ")判断。