#include<iostream>
using namespace std;

void zigzag(int**M, int N)
{
    /** example N=5 结果
    *    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
    **/
    /*prestep表示上一步的动作，其值及其对应关系如下：
    case 1:上一步向右走
    case 2;上一步左下走
    case 3:上一步向下走
    case 4:上一步右上走*/
    int prestep;
    int count = 0;
    int i = 0;
    int j = 0;
    *(*(M + i) + j) = count;
    count++;
    prestep = 4;
    while (count < N*N)
    {
        if (i == 0)//上边界走法
        {
            if (j == N - 1)
            {
                if (prestep == 1)//上一步右，接着左下
                {
                    i++; j--;
                    prestep = 2;
                }
                else if (prestep == 4)
                {
                    i++;
                    prestep = 3;
                }
            }
            else if (prestep == 4)//上一步右上方向走，则现在向右走一步;
            {
                j++;
                prestep = 1;
            }
            else if (prestep == 1)//上一步向右走，现在需要向左下走一步;
            {
                i++;
                j--;
                prestep = 2;
            }
            else
            {
                cerr << "error 1!" << endl;
                return;
            }
        }

        else if (i == N - 1)//下边界走法
        {
            if (prestep == 2)//上一步左下方向，则向右走
            {
                j++;
                prestep = 1;
            }
            else if (prestep == 1 || prestep == 3)//上一步向右走，则像右上走;
            {
                i--;
                j++;
                prestep = 4;
            }
            else
            {
                cerr << "error 2!" << endl;
                return;
            }
        }
        else if (j == 0)//左边界
        {
            if (prestep == 2)//上一步左下，这一步向下
            {
                i++;
                prestep = 3;
            }
            else if (prestep == 3)//上一步向下，这一步右上
            {
                i--;
                j++;
                prestep = 4;
            }
            else
            {
                cerr << "error 3!" << endl;
                return;
            }
        }
        else if (j == N - 1)//右边界
        {
            if (prestep == 4)//上一步右上，这一步向下
            {
                i++;
                prestep = 3;
            }
            else if (prestep == 3 || prestep == 1)//上一步向下，这一步左下
            {
                i++; j--;
                prestep = 2;
            }
            else
            {
                cerr << "error 4!" << endl;
                return;
            }
        }
        else
        {
            if (prestep == 2)//上一步左下，接着左下
            {
                i++; j--;
                prestep = 2;
            }
            else if (prestep == 4)//上一步右上，这一步接着右上
            {
                i--; j++;
                prestep = 4;
            }
            else
            {
                cerr << "error 5!" << endl;
                return;
            }
        }
        *(*(M + i) + j) = count++;
    }
}
int main()
{   
    int N;
    cout << "please input N:";
    cin >> N;
    int **M = (int**)malloc(sizeof(int *)*N);
    for (int i = 0; i < N; i++)
    {
        *(M + i) = (int *)malloc(sizeof(int)*N);
    }
    zigzag(M, N);
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cout << *(*(M+i)+j) << "\t";
        }
        cout << endl;
    }
    for (int i = 0; i < N; i++)
    {
        free(*(M + i));
    }
    free(M);
}