Z字形扫描算法详解与实现

Z字形扫描算法详解与实现

引用

CSDN

1.

https://m.blog.csdn.net/2401_87338545/article/details/143252513

Z字形扫描（Zigzag Scan）是一种常见的图像编码算法，用于将方形矩阵转换为一维序列。本文将通过一个具体的4x4矩阵示例，详细讲解Z字形扫描的实现过程，并给出完整的C++代码实现。

一、题目描述

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

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

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

二、代码实现

#include<bits/stdc++.h>
using namespace std;
const int N = 505;
int a[2*N][2*N];

int main() {
    int n;
    scanf("%d",&n);
    for(int i = 0; i < n; i ++) {
        for(int j = 0; j < n; j ++) {
            scanf("%d",&a[i][j]);
        }
    }
    int dr = 0,dx[] = {0,1,1,-1},dy[]={1,-1,0,1};
    // 偏移方向（也是偏移量下标）， 偏移量 
    // 先输出原点坐标
    printf("%d ",a[0][0]);
    int x = 0, y = 1; // 初始化坐标
    for(int i = 0; i <(2*n-1)*(2*n-1)/2; i ++) {
        if(x<n&&y<n) {
            printf("%d ",a[x][y]);
        }
        int l = x+dx[dr], r = y+dy[dr];
        // 判断偏移条件是否符合，不符合改变方向重新偏移 
        if(dr == 0 || dr == 2 || r<0 || l<0 || r>=n || l>=n) {
            dr = (dr+1)%4;//
            l = x+dx[dr], r = y+dy[dr];
        }
        x = l, y = r; // 偏移 
    } 
    return 0; 
}

三、图文直观笔记

为了更好地理解Z字形扫描的过程，我们可以将数组的规模扩大，以便更清晰地看到完整的搜索路线。具体来说，我们使用一个2N x 2N的数组来存储原始的N x N矩阵，这样可以更直观地展示Z字形扫描的路径。

在这个扩展的数组中，我们使用以下变量来帮助实现Z字形扫描：

• 坐标：x 和 y 用于表示当前扫描的位置。
• 偏移方向：dr 用于表示当前的扫描方向，它会在四个方向之间循环（使用模运算实现）。
• 偏移量数组：dx[] 和 dy[] 分别存储了四个方向的偏移量。
• 临时存储坐标：l 和 r 用于存储偏移后的坐标，以便在需要改变方向时重新计算。

通过这种方式，我们可以清晰地看到Z字形扫描的完整路径，并且能够处理各种边界情况，确保扫描过程的正确性。