14年12月CCF真题2－Z字形扫描

问题描述

在图像编码的算法中,需要将一个给定的方形矩阵进行Z字形扫描(Zigzag Scan)。给定一个n×n的矩阵,Z字形扫描的过程如下图所示:

对于下面的4×4的矩阵,

1539

3756

9464

7313

对其进行Z字形扫描后得到长度为16的序列: 1539739547366413 请实现一个Z字形扫描的程序,给定一个n×n的矩阵,输出对这个矩阵进行

Z字形扫描的结果。输入格式

输入的第一行包含一个整数n,表示矩阵的大小。输入的第二行到第n+1行每行包含n个正整数,由空格分隔,表示给定的矩阵。

输出格式

输出一行,包含n×n个整数,由空格分隔,表示输入的矩阵经过Z字形扫描后的结果。

输入样例
4
1539
3756
9464
7313
输出样例
1539739547366413

评测用例规模与约定 1≤n≤500,矩阵元素为不超过 1000 的正整数。

定义四种动作1234，表示4种移动方式。

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 int main(){
 6     int n;
 7     cin>>n;
 8     int s[n][n];
 9     for(int i =0;i<n;i++)
10         for(int j =0;j<n;j++)
11             cin>>s[i][j];
12     int x(0),y(0);
13     int move=1;
14     while(x!=n-1 || y!=n-1)
15     {
16         cout<<s[x][y]<<" ";
17         switch (move)
18         {
19             case 1:
20                 y++;
21                 if(x==0)
22                     move=2;
23                 else
24                     move=4;
25                 break;
26             case 2:
27                 x++;
28                 y--;
29                 if(y==0 && x!=n-1)
30                     move=3;
31                 else if(x==n-1)
32                     move=1;
33                 break;
34             case 3:
35                 x++;
36                 if(y==0)
37                     move=4;
38                 else
39                     move=2;
40                 break;
41             case 4:
42                 x--;
43                 y++;
44                 if(x==0 && y!=n-1)
45                     move=1;
46                 else if(y==n-1)
47                     move=3;
48                 break;
49         }
50     }
51     cout<<s[n-1][n-1];
52     return 0;
53 }