试题编号： 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的正整数。
解析：
这道题，刚看到后有点懵，读完题还不太清楚题目里的Z字形到底是怎么个扫描法。刚开始还是没头绪的，但是自己在纸上画了3种情况，找到规律还是很容易解出来的。这道题思路有很多，比如你可以通过判断是否走到边界来判断是否要改变方向。但是我觉的这道题作为第2题，通过找规律解出来是最节省时间的。
我先来列举3种情况的走法：
n=3时：右1 -> 左下1 -> 下1 -> 右上2 -> 下1 -> 左下1 ->右1
n=4时：右1 -> 左下1 -> 下1 -> 右上2 -> 右1 -> 左下3 -> 右1 -> 右上2 -> 下1 -> 左下1 ->右1
n=5时：右1 -> 左下1 -> 下1 -> 右上2 -> 右1 -> 左下3 -> 下1 -> 右上4 -> 下1 -> 左下3 -> 右1 -> 右上2 ->下1 -> 左下1 -> 右1
规律就是：
总共移动的方向有4个，分别为向右，向左下，向下，向右上。
这4个方向可以分成2组，一组为向右和向下，每次都只移动1个步长。一组为左下和右上，
我们可以发现，运动方向刚开始是向右，然后是左下，下，右上。
斜方向的移动步长是先递增后递减。
拿n=5举例，斜方向的步长分别为： 1 2 3 4 3 2 1
方向的变换我们可以得出：右方向和下方向是交替的，但是有一个地方特殊，就是当移动完对角线时，方向是不变化的，我已经用粗体标出了。拿n=5举例吧，当第七步向下移动一个单位长度，再向右上方向移动4个单位长度后，按照之前的规律，紧接的一下步应该变成右1，但是没有发生改变。
左下和右上方向是一直交替进行的，并且每次都穿插在向右或向下移动之后。
所以我们可以分两步来遍历整个矩阵，沿右上方向的斜对角线分开，先遍历左半部分，再遍历右半部分。
代码如下：
#include<iostream>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
int n; //存储输入的n值
cin>>n;
int a[n][n]; //存储输入的矩阵
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cin>>a[i][j];
}
}
int m,k; //m记录访问的需要访问元素的横坐标，k为纵坐标
m=k=0;
cout<<a[k][m]<<" "; //访问第一个元素
int flag1=-1; //记录访问方向的标志位，-1为向右，1为向下
int flag2=-2; //访问方向的标志位，-2为左下，2为右上
int s1=1; //记录左下和右上访问方向的步长
for(int i=0;i<n-1;i++) //先遍历左上半边
{
if(flag1==-1) //向下访问
{
m++; //对应横坐标加1
}
else //向右访问
{
k++;
}
if(i!=n-2) //如果不是最后一次，则将下次访问方向改变
flag1=-flag1;
cout<<a[k][m]<<" ";
for(int j=0;j<s1;j++) //斜方向访问
{
if(flag2==-2) //左下
{
m--;
k++;
}
else //右上
{
m++;
k--;
}
cout<<a[k][m]<<" ";
}
if(i!=n-2) //若不是最后一次，则下次步长加1,否则减1
s1++;
else
s1--;
flag2=-flag2; //下次反问的斜方向发生改变
}
for(int i=0;i<n-1;i++) //遍历右下半部分
{
if(flag1==-1)
{
m++;
}
else
{
k++;
}
cout<<a[k][m]<<" ";
flag1=-flag1;
for(int j=0;j<s1;j++)
{
if(flag2==-2)
{
m--;
k++;
}
else
{
m++;
k--;
}
cout<<a[k][m]<<" ";
}
s1--;
flag2=-flag2;
}
return 0;
}