题目描述

在图像编码的算法中，需要将一个给定的方形矩阵进行 Z 字形扫描(Zigzag Scan)。

给定一个 n×n 的矩阵，Z 字形扫描的过程如下图所示：

对于下面的 4×4 的矩阵，

1 5 3 9
3 7 5 6
9 4 6 4
7 3 1 3
对其进行 Z 字形扫描后得到长度为 16 的序列：1 5 3 9 7 3 9 5 4 7 3 6 6 4 1 3。

请实现一个 Z 字形扫描的程序，给定一个 n×n 的矩阵，输出对这个矩阵进行 Z 字形扫描的结果。

输入样例

4
1 5 3 9
3 7 5 6
9 4 6 4
7 3 1 3

输出

1 5 3 9 7 3 9 5 4 7 3 6 6 4 1 3

(枚举) $O(n^2)$

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N=505;
int A[N][N];

int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>A[i][j];
        }
    }

    int t=0;
    while(t<n){ //输出对角线和左边的元素 
        for(int i=0;i<=t;i++){
            if(t%2==0){ //判断遍历方向 
                cout<<A[t-i][i]<<" ";
            }
            else cout<<A[i][t-i]<<" ";
        }
        t++;
    }

    while(t<2*n-1){  //输出对角线右边的元素 (共2n-1条对角线)
        for(int i=n-1;i>t-n;i--){
            if(t%2==0){ //判断遍历方向        
                cout<<A[i][t-i]<<" ";
            }   
            else cout<<A[t-i][i]<<" "; 
        }
        t++;
    }

    return 0;
}