[已解决]实在是写不出来Z字形扫描

zmLau0727

标题       
Z字形扫描

类别       
数组

时间限制       
1S

内存限制       
256Kb

问题描述       
在图像编码的算法中，需要将一个给定的方形矩阵进行Z字形扫描(Zigzag Scan)。给定一个m×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<100)，表示矩阵的行和列数；接下来的n行数据，每行分别为n个整数值(每个整数值都不超过1000)，即矩阵的值

输出说明       
在一行上输出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

最佳答案

月排行榜 / 总排行榜

jackz007

2019-12-23 02:46:05

#include <stdio.h>

main(void)
{
        int i , j , k , n                                   ;
        scanf("%d" , & n)                                   ;
        int d[n * n] , e[n * n]                             ;
        for(k = 0 ; k < n * n ; k ++) scanf("%d" , & d[k])  ;
        e[0] = d[0]                                         ;
        for(i = 0 , j = 0 , k = 1 ; k < n * n ;) {
                if(! i || i == n - 1) j ++                  ;
                else i ++                                   ;
                if(! i || j == n - 1) {
                        for(;; i ++ , j --) {
                                e[k ++] = d[i * n + j]      ;
                                if(i == n - 1 || ! j) break ;
                        }
                } else {
                        for(;; i -- , j ++) {
                                e[k ++] = d[i * n + j]      ;
                                if(! i || j == n - 1) break ;
                        }
                }
        }
        printf("%d" , e[0])                                 ;
        for(k = 1 ; k < n * n ; k ++) printf(" %d" , e[k])  ;
        printf("\n")                                        ;
}

        编译、运行实况：

C:\Bin>g++ -o x x.c

C:\Bin>x
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

C:\Bin>

跳转到最佳答案楼层

jackz007

      不了解 z 字形扫描。
      楼主，你给出的样例元素有重复，所以，看不出规律，假如样例是

A   B   C   D
E   F   G   H
I   J   K   L
M   N   O   P

      那么，对应的 z 字形扫描输出的结果应该是什么？

人造人

jackz007 发表于 2019-12-22 22:23
不了解 z 字形扫描。
      楼主，你给出的样例元素有重复，所以，看不出规律，假如样例是

https://blog.csdn.net/Shenpibaipao/article/details/78863451

jackz007

#include <stdio.h>

main(void)
{
        int i , j , k , n                                   ;
        scanf("%d" , & n)                                   ;
        int d[n * n] , e[n * n]                             ;
        for(k = 0 ; k < n * n ; k ++) scanf("%d" , & d[k])  ;
        e[0] = d[0]                                         ;
        for(i = 0 , j = 0 , k = 1 ; k < n * n ;) {
                if(! i || i == n - 1) j ++                  ;
                else i ++                                   ;
                if(! i || j == n - 1) {
                        for(;; i ++ , j --) {
                                e[k ++] = d[i * n + j]      ;
                                if(i == n - 1 || ! j) break ;
                        }
                } else {
                        for(;; i -- , j ++) {
                                e[k ++] = d[i * n + j]      ;
                                if(! i || j == n - 1) break ;
                        }
                }
        }
        printf("%d" , e[0])                                 ;
        for(k = 1 ; k < n * n ; k ++) printf(" %d" , e[k])  ;
        printf("\n")                                        ;
}

        编译、运行实况：

C:\Bin>g++ -o x x.c

C:\Bin>x
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

C:\Bin>

zmLau0727

jackz007 发表于 2019-12-23 02:46
编译、运行实况：

老哥，能麻烦你注释一下吗，我就说看不懂这个过程

jackz007

zmLau0727 发表于 2019-12-23 11:41
老哥，能麻烦你注释一下吗，我就说看不懂这个过程

      注释也不见得能解决你的问题，这样吧，我把编程的思想总结一下供你参考：

1、把一维数组当成二维数组来处理，因为这样更直观，代码中的变量 i、j 就对应矩阵的行号和列号，一维、二维索引的对应关系为 i * n + j

2、扫描的起点是矩阵的左上角，对应于 i = 0， j = 0，也就是 d[0]，直接获取就行了，后面就开始循环,循环的目标是让 e[] 遍历到 d[] 中的每一个元素，以 k 为索引，当 k 的值为 n x n 时，循环遍历就可以结束了。每次循环前，先判断起点位置，当 i == 0 或 i == n - 1 的时候，说明起点位于矩阵第一或最后一行，这时，列数 j = j + 1，否则，起点一定位于第一列或最后一列，这时，行数 i = i + 1；

3、Z 字形扫描路径分为上行和下行，当起点位于第一行(i = 0)或最后一列(j = n - 1)时，为下行方向，在这个方向上，i 值渐增 j 值渐减，增减不能突破  i = n - 1 和  j = 0  的范围；否则为上行方向，在这个方向上，i 值渐减 j 值渐增，增减不能突破 i = 0 和 j = n - 1 的范围。