蛇形矩阵-螺旋填数

Posted on

题目描述

题目链接：N诺/DreamJudge 1216

输入一个整数 n（1 ≤ n ≤ 20），输出 n×n 的螺旋方阵。数字从 1 开始沿顺时针螺旋方向依次填入。

核心思路

模拟填数过程：定义四个方向，沿着当前方向一直走，撞墙或碰到已填的格子就拐弯。

关键是两个问题：

  1. 怎么表示”拐弯”——方向数组 + 循环取模
  2. 怎么判断”该拐了”——越界 or 已访问

方向数组的设计

四个方向按顺序定义：↓ 右 上 左（顺时针螺旋，从向下开始）

1
2
int dx[4] = {1, 0, -1, 0};   // x 的变化量（行）
int dy[4] = {0, 1, 0, -1};   // y 的变化量（列）
index dx dy 方向
0 1 0 向下
1 0 1 向右
2 -1 0 向上
3 0 -1 向左

方向数组的核心优势：拐弯只需要 index = (index + 1) % 4，不需要写四个 if-else。

拐弯的判断

填数时，先计算下一步的坐标 (xx, yy)，如果满足以下任一条件就拐弯：

  1. xx < 0 || xx >= n — 超出上下边界
  2. yy < 0 || yy >= n — 超出左右边界
  3. mtx[xx][yy] != -1 — 格子已经被填过
1
2
3
4
5
6
7
8
9
int xx = x + dx[index];
int yy = y + dy[index];
if (xx < 0 || xx >= n || yy < 0 || yy >= n || mtx[xx][yy] != -1) {
    index = (index + 1) % 4;     // ⚠️ 拐弯，循环取模
    xx = x + dx[index];           // 用新方向重新算
    yy = y + dy[index];
}
x = xx;
y = yy;

⚠️ 为什么 mtx 要初始化为 -1

因为数字从 1 开始填，0 也是有意义的数字。用 -1 表示”还没填过”，不会和实际值冲突。

C++ 输出对齐

题目输出要求每个数占固定宽度，左对齐：

1
cout << left << setw(4) << mtx[i][j];

三个要素拆开讲：

setw(n) — 设置字段宽度

1
2
cout << setw(4) << 1;    // 输出 "   1"（右对齐，默认）
cout << setw(4) << 25;   // 输出 "  25"

关键坑点：setw 只对紧跟着的那一次输出生效，用完即失效。

1
2
cout << setw(4) << 1 << 2;          // 只有 1 占 4 格，2 不会
cout << setw(4) << 1 << setw(4) << 2; // ⚠️ 每个都要写

left / right — 对齐方向

1
2
cout << left << setw(4) << 1;   // "1   "  左对齐
cout << right << setw(4) << 1;  // "   1"  右对齐（默认）

left 和 right 是粘性的——设置一次后一直有效，不需要每行重复。

setfill() — 填充字符（扩展）

默认用空格填充，可以改成其他字符：

1
2
cout << setfill('0') << setw(4) << 25;  // "0025"
cout << setfill(' ') << setw(4) << 25;  // "  25"（改回来）

setfill 也是粘性的。

完整代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int main() {
    int n;
    cin >> n;
    vector<vector<int>> mtx(n, vector<int>(n, -1));
    int x = 0, y = 0;
    int index = 0;

    for (int i = 1; i <= n * n; i++) {
        mtx[x][y] = i;

        int xx = x + dx[index];
        int yy = y + dy[index];

        // ⚠️ 判断是否需要拐弯
        if (xx < 0 || xx >= n || yy < 0 || yy >= n || mtx[xx][yy] != -1) {
            index = (index + 1) % 4;
            xx = x + dx[index];
            yy = y + dy[index];
        }
        x = xx;
        y = yy;
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << left << setw(4) << mtx[i][j];
        }
        cout << endl;
    }
}

扩展：四种常见螺旋变体

螺旋矩阵根据起始方向和旋转方向不同，有四种常见变体。核心差异只在方向数组的顺序：

变体 起始方向 dx 数组 dy 数组 适用题目
顺时针从下 ↓ {1,0,-1,0} {0,1,0,-1} 本题
顺时针从右 → {0,1,0,-1} {1,0,-1,0} LeetCode 59
逆时针从下 ↓ {1,0,-1,0} {0,-1,0,1} —
逆时针从右 → {0,-1,0,1} {1,0,-1,0} —

搞清题目要求的起点和旋转方向，改方向数组就行，其他逻辑不变。

总结

要点 说明
方向数组 dx[4] + dy[4]，按顺序存放四个方向
拐弯条件 越界 or 已填（mtx != -1）
方向切换 index = (index + 1) % 4
初始化 用 -1 标记未填（因为数字 ≥1）
setw(n) 只对下一次输出生效，每次都要写
left/right 粘性设置，影响之后所有输出
setfill(c) 粘性设置，可改填充字符