题目描述

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

灵感来自洛谷的的一道题：P1014 [NOIP1999 普及组] Cantor 表

#include <iostream>
using namespace std;

const int N = 1010;

int n;
int arr[N][N];
int main () {
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> arr[i][j];

    int i = 1;
    while (i <= n) {
        int a, b;
        if (i % 2 == 0) {
            a = 1;
            b = i;
            while (a <= i) {
                cout << arr[a][b] << " ";
                a ++;
                b--;
            }
        }
        else {
            a = i;
            b = 1;
            while (a >= 1) {
                cout << arr[a][b] << " ";
                a --;
                b ++;
            }
        }
        i ++;
    }

    i = n - 1;
    int cnt = 1;
    while (i >= 1) {
        int a, b;
        if (i % 2 == 0) {
            a = 1;
            b = i;
            while (a <= i) {
                cout << arr[a + cnt][b + cnt] << " ";
                a ++;
                b--;
            }
        }
        else {
            a = i;
            b = 1;
            while (a >= 1) {
                cout << arr[a + cnt][b + cnt] << " ";
                a --;
                b ++;
            }
        }
      cnt++;
        i--;
    }
    return 0;
}