CSP201412-2 Z字形扫描

题目传送门

题目分析
  所谓的Z字形扫描，实际上就是斜着对方阵进行遍历。下面以下图5x5的方阵为例进行说明。

  如图中所示，在5x5的方阵上共画了9条斜线，这表明需要斜着遍历9次。在遍历的时候，我们可以发现一些规律。

• 奇数次遍历是从左下角到右上角，而偶数次遍历是从右上角到左下角。
• 当遍历的次数pass小于等于n时，每一趟遍历所输出的元素个数恰好等于遍历次数，当遍历次数pass大于n时，每一趟遍历所输出的元素个数为2 * n - pass。对于上图而言，第4次遍历所输出的元素个数为4(图中标号为④的斜线所穿过的方格数)，第7次遍历所输出的元素个数为2 * 5 - 7 = 3。

  有了上述的两条规律，我们就可以进行算法的设计了。首先约定方阵的左上角为二维数组的第0个元素，数组下标都是从0开始，且存储方阵的数组名是matrix，每输出完一条红色斜线所穿过的元素称为一趟。
  对于第pass次遍历，记此次遍历输出的元素个数为number。当pass是偶数时，此趟遍历是从图中所示红色斜线的右上角到左下角，右上角的第一个元素的第一维坐标j为min(pass-1,n-1)，第二维坐标i为pass-1-j。同理，当pass为奇数时，左下角第一个元素的第二维坐标i为min(pass-1,n-1)，第一维坐标j为pass-1-i。有了每趟输出时的起始位置，后面要么是i++,j--，要么是j++,i--，同时再用number控制输出的次数，即可将上图中任意一条红线所穿过的元素进行输出。

源代码

#include <bits/stdc++.h>
using namespace std;
int matrix[500][500];
int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> matrix[i][j];
	for (int pass = 1; pass < 2 * n; pass++) {
		int i, j;
		int number;//这一趟有几个数字
		if (pass >= n)
			number = 2 * n - pass;
		else
			number = pass;
		if (pass % 2 == 0) {//pass为偶数
			j = min(pass - 1, n - 1);
			i = pass - 1 - j;
			while (number--) {
				cout << matrix[i][j] << " ";
				i++;
				j--;
			}
		}
		else {//pass为奇数
			i = min(pass - 1, n - 1);
			j = pass - 1 - i;
			while (number--) {
				cout << matrix[i][j] << " ";
				i--;
				j++;
			}
		}
	}
}

题目

问题描述
　　在图像编码的算法中，需要将一个给定的方形矩阵进行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的正整数。