问题描述

　　给定一个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的正整数。  

大致思路

　　假定mp[i][j]是当前要输出的项。

　　注意到，Z字形扫描的过程中 i，j 之和会从0到 2*n-2 变化，于是可以用 k 表示 i，j 之和，构成一个关于 k 大循环。

　　然后，在每个大循环中扫描的方向有两个：右上->左下；左下到右上。这可以通过定义一个 flag，或者根据 k 的奇偶来区分。

　　　　对于 右上->左下 这一扫描方式，可初始化 i=(k<n)?0:k-n+1 （k>n时会从矩阵的右边界开始扫描），此时可用 k-i 来表示 j 。随着 i 的不断递增（直到 i 或 j 越界）即可完成当前扫描。

　　　　同理，对于 右上->左下 这一扫描方式，可初始化 j=(k<n)?0:k-n+1 用 k-j 表示 i，并随着 j 的自增完成当前扫描。

 

具体实现

AC代码如下：

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<iostream>
 4 using namespace std;
 5 const int N=500;
 6 int mp[N][N];
 7 int main()
 8 {
 9     int n;
10     scanf("%d",&n);
11     for(int i=0;i<n;i++){
12         for(int j=0;j<n;j++){
13             scanf("%d",&mp[i][j]);
14         }
15     }
16     bool flag=0;
17     for(int k=0;k<2*n-1;k++){
18         int i,j;
19         if(flag){
20             i=(k<n)?0:k-n+1;
21             for(;i<n&&k-i>=0;i++){
22                 printf("%d ",mp[i][k-i]);
23             }
24         }
25         else{
26             j=(k<n)?0:k-n+1;
27             for(;j<n&&k-j>=0;j++){
28                 printf("%d ",mp[k-j][j]);
29             }
30         }
31         flag=1-flag;
32     }
33     return 0;
34 }