CCF CSP 201412-2.Z字形扫描

问题描述

　　在图像编码的算法中，需要将一个给定的方形矩阵进行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字形扫描中，共有4种移动方向：向右、向左下、向下以及向右上。

扫描的第一步向右走，接下来按照如下规则移动：

1.当前向右移动。若碰到下边界，则下一步向右上方走；否则，下一步向左下方走。

2.当前向左下方移动。若碰到下边界，则下一步向右走；若碰到左边界，则下一步向下走；否则，继续向左下方走。

3.当前向下移动。若碰到右边界，则下一步向左下方走；否则，下一步向右上方走。

4.当前向右上方移动。若碰到右边界，则下一步向下走；若碰到上边界，则下一步向右走；否则，继续向右上方移动。

#include <cstdio>

int main() {
	int n;
	scanf("%d", &n);

	int matrix[n][n];
	int result[n * n];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &matrix[i][j]);
		}
	}
	// 下一步的移动方向，1:向右,2:左下方,3:向下,4:右上方
	int direction = 1;
	int index = 0, i = 0, j = 0;
	while (i < n && j < n) {
		result[index++] = matrix[i][j];
		if (direction == 1) {
			j++;
			// 若碰到下边界，则向右上方；否则，向左下方
			if (i == n - 1) {
				direction = 4;
			} else {
				direction = 2;
			}
		} else if (direction == 2) {
			i++;
			j--;
			// 若碰到下边界，则向右行;若碰到左边界,则向下行
			if (i == n - 1) {
				direction = 1;
			} else if (j == 0) {
				direction = 3;
			}
		} else if (direction == 3) {
			i++;
			// 若碰到右边界，则向左下方;否则，向右上方
			if (j == n - 1) {
				direction = 2;
			} else {
				direction = 4;
			}
		} else {
			i--;
			j++;
			// 若碰到右边界，则向下；若碰到上边界，向右
			if (j == n - 1) {
				direction = 3;
			} else if (i == 0) {
				direction = 1;
			}
		}
	}

	for (int j = 0; j < n * n; j++) {
		if (j > 0) {
			printf(" ");
		}
		printf("%d", result[j]);
	}
	printf("\n");
	return 0;
}