[ccf/csp题]201412-2 Z字形扫描

落日映苍穹つ 2022-06-06 05:38 185阅读 0赞

**试题编号**： 201412-2  
**试题名称**： Z字形扫描  
**时间限制**： 2.0s  
**内存限制**： 256.0MB  
**问题描述**：  
**问题描述**  
　　在图像编码的算法中，需要将一个给定的方形矩阵进行Z字形扫描(Zigzag Scan)。给定一个n×n的矩阵，Z字形扫描的过程如下图所示：

![这里写图片描述][SouthEast]

对于下面的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字形扫描后的结果。  
**样例输入**  
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  
**评测用例规模与约定**  
　　1≤n≤500，矩阵元素为不超过1000的正整数。

## **解析：** ##

这道题，刚看到后有点懵，读完题还不太清楚题目里的Z字形到底是怎么个扫描法。刚开始还是没头绪的，但是自己在纸上画了3种情况，找到规律还是很容易解出来的。这道题思路有很多，比如你可以通过判断是否走到边界来判断是否要改变方向。但是我觉的这道题作为第2题，通过找规律解出来是最节省时间的。

我先来列举3种情况的走法：

n=3时：右1 -> 左下1 -> **下1** \-> 右上2 -> **下1** \-> 左下1 ->右1  
n=4时：右1 -> 左下1 -> 下1 -> 右上2 -> **右1** \-> 左下3 -> **右1** \-> 右上2 -> 下1 -> 左下1 ->右1  
n=5时：右1 -> 左下1 -> 下1 -> 右上2 -> 右1 -> 左下3 -> **下1** \-> 右上4 -> **下1** \-> 左下3 -> 右1 -> 右上2 ->下1 -> 左下1 -> 右1

规律就是：  
总共移动的方向有4个，分别为向右，向左下，向下，向右上。  
这4个方向可以分成2组，一组为向右和向下，每次都只移动1个步长。一组为左下和右上，  
我们可以发现，运动方向刚开始是向右，然后是左下，下，右上。  
斜方向的移动步长是先递增后递减。  
拿n=5举例，斜方向的步长分别为： 1 2 3 4 3 2 1  
方向的变换我们可以得出：右方向和下方向是交替的，但是有一个地方特殊，就是当移动完对角线时，方向是不变化的，我已经用粗体标出了。拿n=5举例吧，当第七步向下移动一个单位长度，再向右上方向移动4个单位长度后，按照之前的规律，紧接的一下步应该变成右1，但是没有发生改变。

左下和右上方向是一直交替进行的，并且每次都穿插在向右或向下移动之后。

所以我们可以分两步来遍历整个矩阵，沿右上方向的斜对角线分开，先遍历左半部分，再遍历右半部分。

代码如下：

#include<iostream>
    using namespace std;
    
    
    int main()
    {
        ios::sync_with_stdio(false);
    
        int n;  //存储输入的n值
        cin>>n;
        int a[n][n];  //存储输入的矩阵
    
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                cin>>a[i][j];
            }
        }
        int m,k;   //m记录访问的需要访问元素的横坐标，k为纵坐标
        m=k=0;
        cout<<a[k][m]<<" ";   //访问第一个元素
        int flag1=-1;    //记录访问方向的标志位，-1为向右，1为向下
        int flag2=-2;    //访问方向的标志位，-2为左下，2为右上
        int s1=1;      //记录左下和右上访问方向的步长
        for(int i=0;i<n-1;i++)   //先遍历左上半边
        {
            if(flag1==-1)  //向下访问
            {
                m++;    //对应横坐标加1
            }
            else     //向右访问
            {
                k++;
            }
            if(i!=n-2)     //如果不是最后一次，则将下次访问方向改变
            flag1=-flag1;
    
            cout<<a[k][m]<<" "; 
    
            for(int j=0;j<s1;j++)   //斜方向访问
            {
                if(flag2==-2)   //左下
                {
                    m--;
                    k++;
                }
                else     //右上
                {
                    m++;
                    k--;
                }
                cout<<a[k][m]<<" ";
            }
            if(i!=n-2)   //若不是最后一次，则下次步长加1,否则减1
            s1++;
            else
            s1--;
    
            flag2=-flag2;    //下次反问的斜方向发生改变
        }
        for(int i=0;i<n-1;i++)   //遍历右下半部分
        {
            if(flag1==-1)    
            {
                m++;
            }
            else
            {
                k++;
            }
            cout<<a[k][m]<<" ";
    
            flag1=-flag1;
            for(int j=0;j<s1;j++)
            {
                if(flag2==-2)
                {
                    m--;
                    k++;
                }
                else
                {
                    m++;
                    k--;
                }
                cout<<a[k][m]<<" ";
    
            }
            s1--; 
            flag2=-flag2;
    
        }
        return 0;
    }

[SouthEast]: /images/20220606/33c87f491f36465aa53ba891918b99be.png