C++-Z字扫描实现(Zigzag Scan)

Z字扫描(Zigzag Scan)

将二维矩阵压缩成行输出：

int index=0;
for(int i=0;i<rows+cols-1;i++){//i是第几条对角线if(i&1){//odd,向下扫描for(int j=max(0,i-cols+1);j<=min(i,row-1);j++){res[index++]=mtx[j][i-j];}//}else{//偶数，向上扫描for(int j=min(i,rows-1);j>=max(0,i-cols+1);j--){res[index++]=mtx[j][i-j];}}
}
//假如是正方形：
int n,index;
for(int i=0;i<2*n-1;i++){if(i&1){//oddfor(int j=max(i,i-n+1);j<=min(i,n-1);j--){res[index++]=mtx[j][i-j];}}else{//偶数for(int j=min(i,n-1);j>=max(i,i-n+1);j++){res[index++]=mtx[j][i-j];}}
}

那么反过来，输入一串数字，变成Z型矩阵：

只需要更改中间赋值代码：

res[index++]=mtx[j][i-j]->mtx[j][i-j]=res[index++]

根据CCF例题中读入扫描数据，将扫描数据按照这样的顺序写入矩阵 M：从左上角$M_{0,0}$开始，接下来填充它的右侧相邻的元素$M_{0,1}$，然后依次向左下方填充直至$M_{1,0}$，接下来从它下侧相邻的元素$M_{2,0}$开始，依次向右上方填充直至 $M_{0,2}$，依次类推，循环往复，直至填充满整个矩阵或用尽所有扫描数据。

由于 Z 字形扫描的路径是从左上角到右下角，数组结尾处可能存在着连续的 0，为了节省空间，可以不存储这些连续的 0。得到的数据被称为扫描数据。

输入的数组元素可能是只有部分，针对它的实现是：

int index=1,n;//n是数组的元素个数=8
for(int i=0;i<15;i++){//2*8-1=15if(i&1){//oddfor(int j=max(0,i-7);j<=min(i,7);j++){int num=0;if(index<=n){cin>>num;index++;}mtx[j][i-j]=num;}}else{for(int j=min(i,7);j>=max(0,i-7);j--){int num=0;if(index<=n){cin>>num;index++;}mtx[j][i-j]=num;}}
}

上面又有可以进行优化的地方。在初始化的时候我们把每个矩阵元素都置为0.所以可以在满足条件之后跳出。

int n;//输入数组元素的个数
int index=1;
bool flag=false;
for(int i=0;i<15;i++){if(i&1){for(int j=max(0,i-7);j<=min(i,7);j++){if(index==n){flag=true;break;}index++;cin>>mtx[j][i-j];}}else{for(int j=min(i,7);j>=max(0,i-7);j--){if(index==n){flag=true;break;}index++;cin>>mtx[j][i-j];}}if(flag)break;
}