3208. Z字形扫描 (偏移量应用)

原题链接
描述
在图像编码的算法中，需要将一个给定的方形矩阵进行 ZZ 字形扫描(Zigzag Scan)。

给定一个 n×nn×n 的矩阵，ZZ 字形扫描的过程如下图所示：

对于下面的 4×44×4 的矩阵，

1 5 3 9
3 7 5 6
9 4 6 4
7 3 1 3

对其进行 ZZ 字形扫描后得到长度为 1616 的序列：1 5 3 9 7 3 9 5 4 7 3 6 6 4 1 3。

请实现一个 ZZ 字形扫描的程序，给定一个 n×nn×n 的矩阵，输出对这个矩阵进行 ZZ 字形扫描的结果。

输入格式

输入的第一行包含一个整数 nn，表示矩阵的大小。

输入的第二行到第 n+1n+1 行每行包含 nn 个正整数，由空格分隔，表示给定的矩阵。

输出格式

输出一行，包含 n×nn×n 个整数，由空格分隔，表示输入的矩阵经过 ZZ 字形扫描后的结果。

数据范围

1≤n≤500,
矩阵元素为不超过 10001000 的正整数。

输入样例：

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

分析
该题以Z字形遍历数组，对于奇数和偶数情况下，边界转向复杂
扩大原二维数组，使边界转向统一

观察旋转方向，设初始方向dr = 0
扩大二维数组，遍历满足在原数组范围内时输出

代码

#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};  //定义(0,1)的方向dr=0  定义偏移量数组
    printf("%d ",a[0][0]);  //先将(0,0)位置的数输出
    int x=0,y=1;  //初始化位置为(0,1)
    for(int i=0;i<(2*n+1)*n;i++){  //循环遍历扩大后的数组
        if(x<n&&y<n){
            printf("%d ",a[x][y]);  //满足在原始数组范围内输出
        }
        int l=x+dx[dr],r=y+dy[dr];  //临时变量判断下一个要遍历的格子坐标(l,r)
        if(dr==0||dr==2||r<0||l<0||r>=n||l>=n){  //如果dr=0或dr=2或(l,r)出界时改变方向
            dr=(dr+1)%4;
            l=x+dx[dr],r=y+dy[dr];
        }
        x=l,y=r;  //更新(x,y)
    }
    return 0;
}

类似使用偏移量做法的题目 756. 蛇形矩阵 (偏移量应用)