Acwing 3208. Z字形扫描 偏移量+扩展图

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

偏移量的做法是：

// 采用偏移的思想，如果
#include 
using namespace std;

const int N = 510;
int a[N][N];

int main(){

    ios::sync_with_stdio(false);cin.tie(0);

    int n;
    cin >> n;

    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            cin >> a[i][j];

    int x = 0, y = 0;
    bool flag = true;//方向一：ture就x--，y++。方向二：false就x++，y--。

    while(x != n || y != n){

        //关于这里为什么需要特判，主要是因为，x和y都有可能大于边界n。
        //（如果还是不清楚的话可以拿我代码模拟下，可以试着删掉下方的if，然后拿例子去调试下）
        if(x < n && y < n)
            cout << a[x][y] << ' ';

        if(flag) x--, y++;
        else x++, y--;
        
        // 因为采用了偏移的思想，越界之后，直接调整
        if(x < 0) {
            x = 0;
            flag = !flag;//x < 0 说明x坐标越界了，把x纠正过来，然后让flag置反
        }
        if(y < 0){
            y = 0;
            flag = !flag;//y < 0 说明y坐标越界了，把y纠正过来，然后让flag置反
        }

    }

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

还有一个做法：

这样就不用进行特判，直接枚举三角形，然后当范围出现在绿色框框以内的时候，就输出

#include 

using namespace std;

const int N = 510;

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

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            scanf("%d", &a[i][j]);
	
	// 枚举横纵坐标之和，1+1=2， 从2开始，到2*n
    for (int i = 2; i <= n * 2; i ++ )      //枚举横纵坐标之和，一共有2n条对角线
    {                                       //此处i表示 x + y
        if (i % 2)                          //偶数即从下往上
        {
            for (int j = 1; j < i; j ++ )   //j表示横坐标，i - 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; j -- )
                if (j >= 1 && j <= n && i - j >= 1 && i - j <= n)
                    printf("%d ", a[j][i - j]);
        }
    }

    return 0;
}

作者：我要出去乱说
链接：https://www.acwing.com/solution/content/36210/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41