题目描述

在图像编码的算法中，需要将一个给定的方形矩阵进行 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 字形扫描的结果。

输入格式
输入的第一行包含一个整数 n，表示矩阵的大小。

输入的第二行到第 n+1 行每行包含 n 个正整数，由空格分隔，表示给定的矩阵。

输出格式
输出一行，包含 n×n 个整数，由空格分隔，表示输入的矩阵经过 Z 字形扫描后的结果。

数据范围
1×n×500，
矩阵元素为不超过 1000 的正整数。

输入样例：
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

思路

路线无非就是先向右,先向下（向上）斜着走，然后向下，向上（向下）斜着走，只是上半部分和下边部分斜着走的方向相反
先走到[0,0]这个点，如果可以向右走一步（j + 1 < n,相当于先预判一下走位），那么向右一步，走完后要么向斜上方走，要么向斜下方走；因为路线先是上半部分是先向斜下方的，所以可以先判断是否是向斜下方走（i + 1 < n ),不行的话就只能向斜上方走。走完后接着就是向下走一步后，然后意思跟前面差不多。

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 505;

int n;
int a[N][N];

int main(){
    scanf("%d",&n);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            scanf("%d",&a[i][j]);
    int i = 0, j = 0;
    cout<<a[i][j]; //先跑到第一个数的位置
    while(!(i == n - 1 && j == n - 1)){ //判断是否到达[n-1,n-1]
        if(j + 1 < n){ //如果可以向右，那么向右走一步
            cout<<" "<<a[i][++j];
            if(i + 1 < n) 
                while(i + 1 < n && j - 1>=0) cout<<" "<<a[++i][--j]; //向下
            else
                while(i - 1 >= 0 && j + 1 < n) cout<<" "<<a[--i][++j];//向上
        }
        if(i + 1 < n){ //如果可以向下，那么向下走一步
            cout<<" "<<a[++i][j];
            if(j + 1 < n)
                while(i - 1 >= 0 && j + 1 < n) cout<<" "<<a[--i][++j];//向上
            else
                while(i + 1 < n && j - 1>=0) cout<<" "<<a[++i][--j]; //向下
        }
    }
    return 0;
}