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，表示矩陣的大小?！　≥斎氲牡诙械降趎+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）