201412-2

2019-11-08 03:11:41

字体：大中小

来源：转载

供稿：网友

问题描述

试题编号：	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字形扫描后的结果。样例输入41 5 3 93 7 5 69 4 6 47 3 1 3样例输出1 5 3 9 7 3 9 5 4 7 3 6 6 4 1 3评测用例规模与约定　　1≤n≤500，矩阵元素为不超过1000的正整数。

问题分析：解题的关键在于如何根据当前方向和当前位置来判断下一步的方向。分析z形扫描的特点发现如下规律：原方向东：下一步可能方向 ①西南 ②东北 ①和②经过分析其条件可知不可能同时成立原方向西南：下一步可能方向①西南 ②南 ③东 ②和③分析其成立条件可知可能会同时成立，同时成立时由题意知应该优先③原方向南：下一步可能方向①西南②东北 ①和②不会同时成立原方向东北：下一步可能方向①东北 ②东 ③南 ②和③同时成立时应该优先③。代码：#include <iostream>using namespace std;/* run this PRogram using the console pauser or add your own getch, system("pause") or input loop */const int EAST=0; //东 const int WESTSOUTH=1; //西南 const int SOUTH=2; //南const int EASTNORTH=3; //东北 int n;int p[501][501];struct Point{int x,y; };int go[][2]={0,1,1,-1,1,0,-1,1 };int main(int argc, char *argv[]) {cin>>n;//1.输入矩形 for(int i=0;i<n;i++){for(int j=0;j<n;j++){cin>>p[i][j];}}//2.从起点开始z字形扫描Point s;s.x=s.y=0;int direc=EAST;cout<<p[s.x][s.y];while(s.x !=n-1 || s.y!=n-1){cout<<" ";Point next;next.x=s.x+go[direc][0];next.y=s.y+go[direc][1];s.x=next.x;s.y=next.y;cout<<p[next.x][next.y];//根据本次的方向以及所在位置判断下一步的方向if(direc == EAST && next.x == 0){direc=WESTSOUTH;}elseif(direc == EAST && next.x== n-1){direc=EASTNORTH;}elseif(direc == WESTSOUTH && next.x == n-1){direc=EAST;}elseif(direc == WESTSOUTH && next.y == 0){direc=SOUTH;}elseif(direc == EASTNORTH && next.y == n-1){direc=SOUTH;}elseif(direc == EASTNORTH && next.x == 0){direc=EAST;}elseif(direc == SOUTH && next.y == 0){direc=EASTNORTH;}elseif(direc == SOUTH && next.y == n-1){direc = WESTSOUTH;}//其余情况都保持方向不变即可}return 0;}代码分析：这个题目中使用了坐标变换数组来方便对坐标的转换。代码参考了林老师的题解，谢谢老师。参考链接：http://blog.csdn.net/tigerisland45/article/details/54773635

上一篇：Intellij IDEA 创建Web项目并在Tomcat中部署运行

下一篇：Mybatis通用DAO设计封装（mybatis）