2020-01-15（ccf201412-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的正整数。

思路
由于路线有一定的规律，所以用 turn来表示
会发生改变方向，并不是一直按照规律来。

Code

#include <iostream>
 using namespace std;
 int main()
 {
    int n;
    cin>>n;
    int a[n][n];
    for(int i=0; i<n; i++)
      for(int j=0; j<n; j++)
        cin>>a[i][j];
    /*   
       若是向右或向下只延伸一个单位 
       一直是按照     右， 左下， 下， 右上   的顺序依次而来 
    */
    
    int turn = 0;
    int i=0;
    int j=0;
    bool flag; //改变方向布尔值 
        for(; ; )
          {
             
             if(i==n-1 && j==n-1) break;
             
             if(turn == 0) // turn为 0 时，  向右 
               {
                  if(j == n-1) //i已经到头，不能向右 
                    {
//                   cout<<a[i][j]<<" ";
                      turn = 2;   
                      flag = true;      
                    } 
                   else
                       {
                         cout<<a[i][j]<<" ";
                         j += 1; 
                         turn = (turn + 1) % 4;
                         if(flag == true) turn = 3;
                       }
               }
             else if(turn == 1) // turn为 1 时，  左下 
               {
                
                  while(j != 0 && i != n-1)
                  {
                     cout<<a[i][j]<<" ";
                     i += 1;
                     j -= 1;    
                 }
//               cout<<a[i][j]<<" ";
                 turn = (turn + 1) % 4;
                 if(flag == true) turn = 0;
               }
             else if(turn == 2)  // turn为 2 时， 向下 
               {
                 if(i == n-1)  // i已经到头，不能向下 
                   {
//                      cout<<a[i][j]<<" ";
                        turn = 0;
                        flag = true;    
                   }
                   else
                   {
                    cout<<a[i][j]<<" ";
                    i += 1; 
                    turn = (turn + 1) % 4;
                    if(flag == true) turn = 1;
                   }
                           
               }
               
            else  //turn为 3 时，  右上
              {
                  while (i != 0 && j != n-1)
                    {
                        cout<<a[i][j]<<" ";
                        i -= 1;
                        j += 1;
                    }
                 turn = (turn + 1) % 4;
                  if(flag == true) turn = 2;
              } 
              
            
          }
       cout<<a[n-1][n-1];
 }