试题编号：201412-2

试题名称：Z字形扫描

时间限制： 2.0s

内存限制： 256.0MB

问题描述

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

样例输入

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

评测用例规模与约定

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

 

解题思路：

 

 

 

 

 

 

 

实现代码自己写的（java）:

　　

1 import java.util.Scanner; 2  3 public class Main { 4     public static void main(String[] args) { 5          6         Scanner sc=new Scanner(System.in); 7          8         int n=sc.nextInt(); 9         10         sc.nextLine();11         12         int num = n + 1;13         14         int[][] matrix=new int[num][num];15         16         for (int i = 1; i < num; i++) {17             18             for (int j = 1; j < num; j++) {19                 20                 matrix[i][j]=sc.nextInt();21             }22             sc.nextLine();23         }24         printIt(matrix);25     }26     27     public static void printIt(int[][]arr){28         29         int n = arr.length;30         31         n--;32         33         for(int i = 1; i<=n; i++){34             35             if(i%2 == 1){36                 37                 int k = 1;38                 39                 for(int j = i; j>0;j--){40                     41                     System.out.print(arr[j][k++]+" ");42                 }43                 44             }else{45                 46                 int k = i;47                 48                 for(int j = 1; j<=i;j++){49                     50                     System.out.print(arr[j][k--]+" ");51                 }52             }53         }54         55         for(int i = n-1; i>0; i--){56             57             if(i%2 == 0){58                 59                 int k = n;60                 61                 for(int j = n-i+1; j<=n;j++){62                     63                     System.out.print(arr[j][k--]+" ");64                 }65                 66             }else{67                 68                 int k = n-i+1;69                 70                 for(int j = n; j>=n-i+1;j--){71                     72                     System.out.print(arr[j][k++]+" ");73                 }74             }75         }76     }77       78 }

运行结果：

　　

 

实现代码2 别人写的（java）：

　　

1 import java.util.Scanner; 2  3 public class Main { 4     public static void main(String[] args) { 5         Scanner sc=new Scanner(System.in); 6         int n; 7         n=sc.nextInt(); 8         int[][] matrix=new int[n][n]; 9         for (int i = 0; i < n; i++) {10             for (int j = 0; j < n; j++) {11                 matrix[i][j]=sc.nextInt();12             }13         }14         15         for (int i = 0; i < n; i++) {16             int row=0;17             int column=0;18             if (i%2==0) {19                 row=i;20                 column=0;21                 System.out.print(matrix[row][column]+" ");22                 while (row-1>=0&&column+1
       
        =0) { 32                     row++;33                     column--;34                     System.out.print(matrix[row][column]+" "); 35                 }36             }37         }38         for (int i = 1; i 
        
         =0&&column+1
         
          =0) {56                         row++;57                         column--;58                         System.out.print(matrix[row][column]+" ");59                     }60                 }61             } else {62                 if (i%2==0) {63                     row=i;64                     column=n-1;65                     System.out.print(matrix[row][column]+" ");66                     while (row+1
          
           =0) {67                         row++;68                         column--;69                         System.out.print(matrix[row][column]+" ");70                     }71                 72                 } else {73                     row=n-1;74                     column=i;75                     System.out.print(matrix[row][column]+" ");76                     while (row-1>=0&&column+1
          
         
        
       

 

运行结果：