Z 字形扫描

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

按副对角线 i+j 分组，并根据对角线编号奇偶交替反向输出。

OJ: shumeng

题目 ID: CSP201412B

难度:入门

标签:模拟二维数组

日期: 2026-07-31 16:21

目录

  1. 形式化题目
  2. 思路
    1. 对角线分组
  3. 代码
  4. 复杂度
  5. 总结

形式化题目

给定一个 n×nn\times n 矩阵，按照 Z 字形遍历顺序输出全部元素。

思路

先看逐条对角线收集再输出的做法：

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-31 16:21
 * update_at: 2026-08-17 22:57
 */
// brute.cpp：小数据暴力解，逐条副对角线收集元素后按方向输出。
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<vector<int> > matrix(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> matrix[i][j];
        }
    }

    vector<int> answer;
    for (int sum = 0; sum <= 2 * n - 2; sum++) {
        vector<int> diagonal;
        for (int row = 0; row < n; row++) {
            int column = sum - row;
            if (0 <= column && column < n) {
                diagonal.push_back(matrix[row][column]);
            }
        }
        if (sum % 2 == 0) reverse(diagonal.begin(), diagonal.end());
        answer.insert(answer.end(), diagonal.begin(), diagonal.end());
    }

    for (int i = 0; i < (int)answer.size(); i++) {
        if (i > 0) cout << ' ';
        cout << answer[i];
    }
    cout << '\n';
    return 0;
}

同一条左下到右上的副对角线满足 row + column = sum。依次处理 sum=0..2n-2：偶数从下向上输出，奇数从上向下输出。

对角线分组

4×4 矩阵的输出序号如下，编号相同的格子属于同一条副对角线：

0 2 6 7
1 5 8 13
3 9 12 14
4 10 11 15

每条对角线内部方向交替：sum 为偶数时从下往上，sum 为奇数时从上往下。边界对角线自然只有一个元素。

代码

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-31 16:21
 * update_at: 2026-08-17 22:57
 */
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<vector<int> > matrix(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> matrix[i][j];
        }
    }

    bool first = true;
    for (int sum = 0; sum <= 2 * n - 2; sum++) {
        int low = max(0, sum - n + 1);
        int high = min(n - 1, sum);
        if (sum % 2 == 0) {
            for (int row = high; row >= low; row--) {
                if (!first) cout << ' ';
                first = false;
                cout << matrix[row][sum - row];
            }
        } else {
            for (int row = low; row <= high; row++) {
                if (!first) cout << ' ';
                first = false;
                cout << matrix[row][sum - row];
            }
        }
    }
    cout << '\n';
    return 0;
}

复杂度

每个矩阵元素只访问一次，时间复杂度为 O(n2)O(n^2)；保存矩阵需要 O(n2)O(n^2) 空间。

总结

Z 字形扫描的本质是“按副对角线分组，再交替反转”。先确定对角线编号和边界，再处理方向，就不会在边缘位置上写出复杂的移动模拟。