题目描述

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

输入格式

输入的第一行包含一个整数 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

写法一 找规律

思路

可以把整个方格分成单数行和双数行，单数行向上、双数行向下进行输出，当然要确保不越界

单数行横纵坐标相加不是2的倍数，双数行的横纵坐标相加是2的倍数

实际上在这个方格阵中，左上角是一种情况，右下角是一种情况，但是如果我们将这个方格阵补全↓

我们就只要考虑左上角那一种情况，然后输出方格阵范围中的数就行了

注意：此题的输入数据范围最大为250 000，数据一旦超过100 000，就尽量使用scanf和printf，可以提高速度

c++代码

#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
    int a[510][510],n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            scanf("%d",&a[i][j]);
        }
    }
    for(int i=2;i<=n*2;i++)
    {
        if(i%2)//如果为双数行
        {
            for(int j=1;j<i;j++)//j为行，从小到大意味着从上到下输出
            {
                if(j>=1&&j<=n&&i-j>=1&&i-j<=n)
                    printf("%d ",a[j][i-j]);
            }
        }
        else//如果为单数行
        {
            for(int j=i-1;j>=1;j--)//j为行，从大到小意味着从下到上输出
            {
                if(j>=1&&j<=n&&i-j>=1&&i-j<=n)
                    printf("%d ",a[j][i-j]);
            }
        }
    }
    return 0;
}

写法二 直接暴力枚举

(做好心理准备，会很长)

这种写法是我自己想出来的，一共有四种方向：0代表向右，1代表向左下，2代表向下，3代表向右下
d用来存储这个格子是通过哪种方式（哪个方向）走过来的，起点默认为从3走过来（因为通过画图可以发现，大部分向右走的格子都是从3过来的）
然后……就是画图，画图可以得到各个格子对应的d，然后找从哪个方向走过来的格子应该走向那个方向
e.g.
4x4的格子：
3->0->1->2->3->3->0->1->1->1->0->3->3->2->1->0
5x5的格子：
3->0->1->2->3->3->0->1->1->1->2->3->3->3->3->2->1->1->0->3->3->2->1->0

由此可得：
d为0的格子可能向1,3的方向走
d为1的格子可能向0,1,2的方向走
d为2的格子可能向1,3的方向走
d为3的格子可能向0,2,3的方向走

然后进行一系列的判断（详细判断见下代码）

#include<iostream>
using namespace std;
int a[1010][1010];
int main()
{
    int n,x=1,y=1;
    cin>>n;
    int dx[4]={0,1,1,-1},dy[4]={1,-1,0,1},d=3;//四个方向及d的初值
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>a[i][j];//输入
        }
    }
    for(int i=1;i<=n*n;i++)
    {
        cout<<a[x][y]<<' ';
        if(d==3)//如果是从3过来的
        {
            if(x==1&&y!=n)//在最上面一行，y!=n表示不在最左边的一列
            {
                x+=dx[0];//向0的方向走
                y+=dy[0];
                d=0;
            }
            else if(y==n)//如果在最左边一列
            {
                x+=dx[2];//向2的方向走
                y+=dy[2];
                d=2;
            }
            else//因为只有向0,2,3的方向走，所以接下来只能向3走
            {
                x+=dx[3];
                y+=dy[3];
                d=3;
            }
        }
        else if(d==0)//如果是从0过来的
        {
            if(x==1)//如果在最上面的一行
            {
                x+=dx[1];//向1的方向走
                y+=dy[1];
                d=1;
            }
            else if(x==n)//如果在最下面一行
            {
                x+=dx[3];//向3的方向走
                y+=dy[3];
                d=3;
            }
        }
        else if(d==1)//如果是从1过来的
        {
            if(y==1&&x!=n)//在最左边一列
            {
                x+=dx[2];//向2的方向走
                y+=dy[2];
                d=2;
            }
            else if(x==n)//在最下面一行
            {
                x+=dx[0];//向0的方向走
                y+=dy[0];
                d=0;
            }
            else//排除两种，接下来只能向1的方向走
            {
                x+=dx[1];
                y+=dy[1];
                d=1;
            }
        }
        else if(d==2)//如果是从2过来的
        {
            if(y==1)//如果在最左边一行
            {
                x+=dx[3];//向3的方向走
                y+=dy[3];
                d=3;
            }
            else if(y==n)//如果在最右边一列
            {
                x+=dx[1];//向1的方向走
                y+=dy[1];
                d=1;
            }
        }
    }
    return 0;
}

写法二纯属自己想的，不喜勿喷O(∩_∩)O~