难 · 模拟

螺旋矩阵

像剥洋葱一样处理网格：打印顶行、再打右列、再倒着打底行、再向上打左列 —— 而最后两步之前，各问一句「还有得剥吗」。整个难度就在这一问。

一句话答案维护 <code>top/bottom/left/right</code>；循环：扫顶行、收缩 top；扫右列、收缩 right；<em>若还有行</em> 倒扫底行；<em>若还有列</em> 向上扫左列。

题目

输入: 第一行是 n 和 m（1 ≤ n, m ≤ 10）。接下来 n 行、每行 m 个整数（−100 到 100）。

输出: 从左上角出发、先向右的螺旋遍历顺序，值之间单个空格，输出在一行。

样例:

输入输出
3 3
1 2 3
4 5 6
7 8 9		1 2 3 6 9 8 7 4 5
1 4
1 2 3 4		1 2 3 4

单行样例放在这里是有意的：扫完顶行后 top 已经越过 bottom，底行扫描必须整个跳过 —— 否则这一行会被打两遍。判题的第二个样例就是陷阱探测器。

你的解答

main.cpp — 你的解答
「运行我的输入」用的自定义输入

判题在浏览器本地运行。死循环会在 3 秒后被自动中断 —— 但还是确保每个循环都有出口。代码随打随存。

卡住了？提示

提示 1 — 一圈 = 四次扫描

顶行从左到右、右列从上到下、底行从右到左、左列从下到上。每次扫完收缩对应边界：top++、right--、bottom--、left++。只要 top <= bottom && left <= right 就继续 —— 区间交叉时洋葱剥完。

提示 2 — 两处复检才是本题

top++ 之后，底行可能已经不存在（单行网格，或螺旋止于一条横带）—— 底行扫描要用 if (top <= bottom) 拦住。对称地，左列扫描用 if (left <= right) 拦住。少了这两处，判题的单行、单列测试就会因为重复访问而挂掉。

提示 3 — 拿非正方形手推一遍

正方形网格把边界 bug 藏得漂漂亮亮 —— 什么都刚好闭合。在纸上手推一遍 2×3 和 3×2，四个循环里的任何错误都会现形。如果你的螺旋在方阵上好好的、上了判题就挂，原因就在这。

题解（先自己试试！） 
#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    int a[12][12];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> a[i][j];

    int top = 0, bottom = n - 1, left = 0, right = m - 1;
    bool first = true;
    while (top <= bottom && left <= right) {
        for (int j = left; j <= right; j++) {
            if (!first) cout << " ";
            cout << a[top][j]; first = false;
        }
        top++;
        for (int i = top; i <= bottom; i++) {
            if (!first) cout << " ";
            cout << a[i][right]; first = false;
        }
        right--;
        if (top <= bottom) {
            for (int j = right; j >= left; j--) {
                if (!first) cout << " ";
                cout << a[bottom][j]; first = false;
            }
            bottom--;
        }
        if (left <= right) {
            for (int i = bottom; i >= top; i--) {
                if (!first) cout << " ";
                cout << a[i][left]; first = false;
            }
            left++;
        }
    }
    cout << endl;
    return 0;
}

「边界收缩式模拟」是旋转、遍历、泛洪填色这类网格问题的共同骨架。和你处理网格的另一种方式 —— 矩阵转置 的整行换下标 —— 对照一下，注意区别：转置动的是下标，螺旋动的是*边*。两者之后的下一项网格技能，是向矩形提问：二维区间求和。

深度解析

为什么这样做对

四条边界(top/bottom/left/right)定义未访问的环;每圈打一圈、每次扫描收缩一条边界。收缩后的两处复检之所以存在,是因为环可能只剩一行或一列薄薄一层 —— 底行打完再打左列,同样的格子会走两遍。

代价

O(n·m):每个格子恰好打印一次,每次扫描的边界算术是常数。网格之外空间 O(1)。

常见错法

  • 底行扫描前少了 if (top <= bottom) 复检(或左列少了复检):单行、单列网格会被打两遍 —— 判题的非方形测试就是为这个准备的。
  • 底行从左到右扫、左列从上到下扫:螺旋方向是交替的,每圈后半程必须倒序循环(j--、i--)。
  • 只信方形测试:3×3 恰好闭合,所有 bug 都被藏住。只有手推 2×3 和 3×2 才能暴露四个循环边界。

下一步

网格处理至今:整行换下标是 矩阵转置,网格组合是 矩阵乘法,走边是本题。之后是向矩形提问:二维区间求和。

记住这两句

  • 一圈 = 四次扫描;每次扫完收缩对应边界。
  • 两处复检(还有行吗?还有列吗?)是非方形测试买来的。
🐞 这段是错的 —— 点开,亲手让它挂一次

底行、左列扫描前没复检 —— 单行会被打两遍

#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    int a[12][12];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> a[i][j];
    int top = 0, bottom = n - 1, left = 0, right = m - 1;
    bool first = true;
    while (top <= bottom && left <= right) {
        for (int j = left; j <= right; j++) { if (!first) cout << " "; cout << a[top][j]; first = false; }
        top++;
        for (int i = top; i <= bottom; i++) { if (!first) cout << " "; cout << a[i][right]; first = false; }
        right--;
        for (int j = right; j >= left; j--) { if (!first) cout << " "; cout << a[bottom][j]; first = false; }  // bug: no guard
        bottom--;
        for (int i = bottom; i >= top; i--) { if (!first) cout << " "; cout << a[i][left]; first = false; }   // bug: no guard
        left++;
    }
    cout << endl;
    return 0;
}