题目描述

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

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

zig.png

对于下面的 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

不知道叫什么法

(相当于遍历了邻接表数组,里边存的边数总和为n^2,所以是O(n^2)的级别) $O(n^2)$

假设下标从1开始，可以找到一个规律.就是说,它的输出路线是 下标之和为2的点 下标之和为3的点 下标之和为4的点…

唯一要注意的地方就是说，下标之和为3、5等奇数的点的路线是按照行的升序（或者我们可以称之为按输入顺序，下面会提.）;而下标之和为2、4等偶数的路线则按照行的降序（或者说按输入顺序，反向输出）.

我直接想到的是用邻接表，但是邻接表从倒着输出不方便，干脆用vector来代替好了，费点空间能过就行,开一个vector数组，或者二维vector,姑且称之为adj.

所以输入时，将a[i][j]插入到adj[i+j]中，就跟插入邻接表似的,就是按照输入顺序了.如上文提到的，输入顺序是行升序.所以奇数的正序输出adj[k]存放的元素,偶数的则倒序输出即可.

看代码很容易看懂的.

C++ 代码

//QAQ
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#define OldTomato ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N = 1001;//因为下标之和要跑到2*n=1000,开1001即可.
int a[N][N];int n;
vector<int> adj[N];//其实应该用邻接表，但是邻接表从尾巴开始遍历比较难.
void fun()
{
    OldTomato;
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n;++j)
        {
            cin>>a[i][j];
            adj[i+j].push_back(a[i][j]); //在输入时顺便插入.
        }
    }
    for(int k=2;k<=n*2;++k) //遍历vector数组.
    {
        if(k%2==0) //偶数要倒置,参考奇数是正好的. 
        {
            for(int i = adj[k].size()-1;i>=0;--i)
            {
                 cout<<adj[k][i]<<' ';
            }
        }
        else  //奇数是正好的,正序输出即可.因为按照输入的顺序插入adj,那么直线会从右上角跑到左下角.
        {     //比如i+j=3.按照a(1,2)、a(2,1)的顺序插入.
            for(auto iter:adj[k])
            {
                cout<<iter<<' ';
            }
        }
    }
    return ;
}
int main(void)
{
    fun();
    return 0;
}