学步园

ZigZag数组就是形如下图的，依次沿对角线增加->减小交替变换的数组

0       1       5       6       14      15      27      28

2       4       7       13      16      26      29      42
3       8       12      17      25      30      41      43
9       11      18      24      31      40      44      53
10      19      23      32      39      45      52      54
20      22      33      38      46      51      55      60
21      34      37      47      50      56      59      61

35      36      48      49      57      58      62      63

对于N*N的zigzag数组，可以分两部分输出：左上三角+对角线，  右下三角

1. 对于左上三角+对角线，我们可以按每一条递增的斜线填充，假如填充到第cross条斜线(从0开始计数)，每一个待填充的a[i][j]，都有i+j = cross。

且j, j的取值范围都是0-cross.

如果cross 是偶数，填充的顺序是从左下，到右上，即列号从0->cross;

如果cross是奇数，填充的顺序是从右上到左下，即行号是从0->cross;

2. 对于右下三角，情况则不同，

    对角线是第N-1条斜线，所以对于对角线右下方，与之平行的对角线，我们看做是N- 2,N -3....条对角线

   且对于每个带填充元素a[i][j]的行列取值 范围也不在是0-cross, 其下限都不能取到0，而依次是1,2,3,。。。，N-1

   所以我们用一个变量limit记录这个下限。此时对于每个填充元素，a[i][j], i+j = limit+N-1

代码如下

#include "stdafx.h"  
#include<iostream>
#include<string>
using namespace std;

void display(int a[][8],int N)
{
     for(int i=0;i<N;i++)
     {
             for(int j = 0;j<N;j++)
             {
                     cout<<a[i][j]<<"\t";
             }
             cout<<endl;
     }
}
int main()
{   
    int a[8][8] = {0};
    int N = 8;
    int count = 0;//记录当前应当填充的元素
    int cross = 0;
    //填充左上三角矩阵，包括对角线，按斜线输出，cross表示的是第几条斜线
	//对于任意一个元素a[i][j]，有i+j = cross
    for(cross = 0;cross<N;cross++)
    {
            if(cross %2 == 0)//如果填充第偶数条斜线，那么输出的方向是做左下角到右上角，终止的条件是行号i==0,或者列好j==N-1
            {
                     for(int row = cross;row>=0;row--)
                     {
                             a[row][cross - row] = count++;
                     }
            }
            else{
                     for(int col = cross;col>=0;col--)//如果填充第奇数数条斜线，那么输出的方向是做右上角到左下角
                     {
                             a[cross - col][col] = count++;
                     }
                 
            }
    }
    //填充右下角矩阵，不包括对角线
    int limit = 1;//记录终止的行列号
    for(cross = N-2;cross>=0;cross--)
    {
            if(cross %2 == 0)
            {
                     for(int row = N-1;row>=limit;row--)
                     {
                             a[row][limit+N-1-row] = count++;
                     }
                     limit++;
            }
            else{
                     for(int col = N-1;col>=limit;col--)
                     {
                             a[limit+N-1-col][col] = count++;
                     }
                     limit++;
                 
            }
    }
    display(a,N);
    getchar();
    return 0;
}