Z字形扫描

题目描述

对于一个 $n\times n$ 的方阵，按照Z字形扫描的顺序输出所有元素。Z字形扫描的路径如下：

从左上角开始，先向右下方向移动，遇到边界后改变方向。方向交替为：右下→右上→右下→右上…

算法思路

模拟Z字形扫描路径：

1. 设当前位置 $(x,y)$，初始为 $(0,0)$
2. 两种扫描方向：向下右上（dx=1, dy=-1）和向右左下（dx=1, dy=-1的对称）
3. 使用方向数组，按题目描述的Z字形规律移动
4. 每次到达边界时转换方向，继续扫描直到遍历完所有元素

更简单的思路：按层遍历，每层有特定的起点和终点方向。

代码实现

#include <bits/stdc++.h>
using namespace std;
 
int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int n;
    cin >> n;
    vector<vector<int>> a(n, vector<int>(n));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> a[i][j];
        }
    }
    
    int x = 0, y = 0;
    // 0: 向右下, 1: 向右上
    int dir = 0;
    int dx[2] = {1, -1};
    int dy[2] = {1, -1};
    
    for(int i = 0; i < n * n; i++){
        cout << a[x][y];
        if(i != n * n - 1) cout << " ";
        
        // 下一步尝试
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        
        // 判断是否越界或方向需要改变
        if(nx < 0 || nx >= n || ny < 0 || ny >= n){
            // 换方向
            if(dir == 0){
                // 从右下角换到右上，需要往下或往右
                if(y + 1 < n) { nx = x; ny = y + 1; }
                else { nx = x + 1; ny = y; }
            }else{
                // 从右上角换到右下，需要往右或往下
                if(x + 1 < n) { nx = x + 1; ny = y; }
                else { nx = x; ny = y + 1; }
            }
            dir = 1 - dir;
        }
        x = nx; y = ny;
    }
    cout << endl;
    return 0;
}

关键点

• Z字形扫描的核心是方向转换逻辑
• 当下一步越界时，需要根据当前位置决定下一个合法位置
• 遍历完所有 $n^2$ 个元素即可

参考

• CCF-CSP认证