Love丶FFC's Blog

CCF-CSP_20141202:Z字形扫描

2019-11-05 18:39:35
阅读:433   •   评论:2
标签:,

问题描述

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

编程语言:Python

解题思想:

1.找出题目的规律,然后在每次移动之前判断一下边界。

2.碰壁后就转向,且上下边界的判定优于左右边界的判定。

时间复杂度:O(n)

IDE代码如下:

  1. N = int(input()) # 输入矩阵的大小
  2. Matrix = [[0 for i in range(N)] for j in range(N)] # 使用循环的方式创建二维数组
  3. for Column in range(N):
  4. Matrix[Column] = [int(n) for n in input().split()]
  5. Row, Column = 1, 1
  6. Point = [] # 经历过的点
  7. Direction = "Up" # 方向向上
  8. for t in range(N * N):
  9. Point.append(Matrix[Row - 1][Column - 1])
  10. if Direction == "Up": # 右上
  11. if Column == N: # 碰到了右边界
  12. Row += 1 # 向下走一格
  13. Direction = "Bottom" # 转向
  14. elif Row == 1: # 碰到了上边界
  15. Column += 1 # 向右走一格
  16. Direction = "Bottom" # 转向
  17. else: # 没碰到边界
  18. Column += 1 # 向右上斜着走一格
  19. Row -= 1
  20. else: # 左下
  21. if Row == N: # 碰到了下边界
  22. Column += 1 # 向右走一格
  23. Direction = "Up" # 转向
  24. elif Column == 1: # 碰到了左边界
  25. Row += 1 # 向下走一格
  26. Direction = "Up" # 转向
  27. else: # 没碰到边界
  28. Column -= 1 # 向左下斜着走一格
  29. Row += 1
  30. print(" ".join(map(str, Point)))
  31.  

评论板

共有 2 条评论

  1. Knitant

    042, Table 5 while levels were significantly higher when del del was compared to wt wt plus wt del p 0 buy cialis online prescription

  2. invoimi

    This definition has enabled to streamline research in the field buy cialis and viagra online The subcellular protein extracts were then analyzed by western blot

--------查看该分类下最新文章--------
^
新版博客正在完善中!域名:http://www.loveffc:8080,点击跳转,完全移植后将去除端口号。

Copyright © 2018 - 2021 FFC的小站 - 滇 ICP 备 18010780 号 - 1

- Powered by WordPress & AliYun · Theme by FFC -

- Environment by Windows & XAMPP · Designed by WebStorm & VSCode -

已运行:

访问量:448993