//螺旋數(shù)組

#include<iostream>
using namespace  std;

//生成一個(gè)n*n維的螺旋數(shù)組,形式如下
/*
1  2  3  4  5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

*/
void spiral_array(int **a,int n)
{
    /*for (int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
            printf("%d  ",a[i][j]);
        printf("\n");
    }*/
    int terminated = n/2;
    int m = 1;
    for (int i = 0; i < terminated; i++)
    {
        for (int j = 0; j < n-i; j++)
        {
            if (a[i][j] == 0)
            {
                a[i][j] = m++;
            }
        }

        for (int j = i+1; j<n-i; j++)
        {
            if (a[j][n-i-1]==0)
            {
                a[j][n-i-1]=m++;
            }
        }

        for (int j = n-i-1; j > i; j--)
        {
            if (a[n-i-1][j]==0)
            {
                a[n-i-1][j]=m++;
            }
        }

        for (int j = n-i-1; j>i; j--)
        {
            if (a[j][i]==0)
            {
                a[j][i]=m++;
            }
        }
        if (n%2==1)
        {
            a[terminated][terminated]=m;
        }
    }

}

int main()
{
    int **a;
    int n;
    printf("請(qǐng)輸入數(shù)組的維數(shù)：");
    scanf("%d",&n);
    //二維數(shù)組動(dòng)態(tài)內(nèi)存分配
    a = (int **)malloc(sizeof(int*)*n);
    for (int i = 0; i < n; i++)
    {
        a[i] = (int *)malloc(sizeof(int)*n);
        for(int j = 0; j < n; j++)
            a[i][j] = 0;
    }

    spiral_array(a,n);

    printf("螺旋數(shù)組：\n");
    for (int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
            printf("%d  ",a[i][j]);
        printf("\n");
    }

    //釋放內(nèi)存
    for (int i = 0; i < n; i++)
    {
        free(a[i]);
    }
    free(a);
    return 0;
}

/*
實(shí)現(xiàn)一個(gè)之字形數(shù)組 ,從1 開始，之字形形成數(shù)組

1  3  4  10
2  5  9  11
6  8  12 15
7  13 14 16

*/

#include<stdio.h>
#include <stdlib.h>
//using namespace  std;


void constructArray(int **array,int N)
{
    //說明，方向坐標(biāo)，每兩個(gè)單位表示一個(gè)反向，
    //一共四個(gè)方向，比如
    //direction[0]、direction[1]表示第一個(gè)方向的x 和 y的走向
    //direction[2]、direction[3]表示第二個(gè)方向的x 和 y的走向
    //direction[4]、direction[5]表示第三個(gè)方向的x 和 y的走向
    //direction[6]、direction[7]表示第四個(gè)方向的x 和 y的走向
    int direction[8]={1,0,-1,1,0,1,1,-1};

    int row = 0, col = 0;
    bool changeDirec = false;
    int index = 1;
    array[row][col] = index;
    while(1)
    {
        for(int i = 0; i < 4; i++)
        {
            if (row == N-1 && col == N-1)//最后一個(gè)位置跳出
                break;
            if(row == N-1 && N%2==1 && changeDirec==false)//奇數(shù)行換方向
            {
                
                direction[0]=0;
                direction[1]=1;
                direction[2]=-1;
                direction[3]=1;
                direction[4]=1;
                direction[5]=0;
                direction[6]=1;
                direction[7]=-1;
                changeDirec = true;
                break;
            }
            if(col == N-1 && N%2==0 && changeDirec==false)//偶數(shù)行換方向
            {
                
                direction[0]=1;
                direction[1]=0;
                direction[2]=1;
                direction[3]=-1;
                direction[4]=0;
                direction[5]=1;
                direction[6]=-1;
                direction[7]=1;
                changeDirec = true;
                break;
            }
            if (changeDirec==false)
            {
                if (i%2==0)
                {
                    row += direction[2*i];
                    col += direction[2*i+1];
                    array[row][col] = ++index;
                }
                else
                {
                    while(1)
                    {
                        if ((direction[2*i]+row)<0 || (col+direction[2*i+1])<0 
                            || (direction[2*i]+row)>=N || (col+direction[2*i+1])>=N)break;//越界判斷
                        row += direction[2*i];
                        col += direction[2*i+1];
                        array[row][col] = ++index;
                    }
                }
            }else 
            {
                if (i%2==0)
                {
                    row += direction[2*i];
                    col += direction[2*i+1];
                    array[row][col] = ++index;
                }
                else
                {
                    while(1)
                    {
                        if ((direction[2*i]+row)<0 || (col+direction[2*i+1])<0 
                            || (direction[2*i]+row)>=N || (col+direction[2*i+1])>=N)break;//越界判斷
                        row += direction[2*i];
                        col += direction[2*i+1];
                        array[row][col] = ++index;
                    }
                }
            }
        }
        if (row == N-1 && col == N-1)
        break;
        
    }



}


int main()
{

    int **array;
    int N;
    printf("請(qǐng)輸入數(shù)組N*N的維數(shù)N：\n");
    scanf("%d",&N);
    //內(nèi)存分配
    array = (int **)malloc(N*sizeof(int *));
    if (array == NULL)
    {
        return -1;
    }
    for (int i = 0; i < N; i++)
    {
        array[i] = (int *)malloc(N*sizeof(int));
        if(array[i]==NULL)return -1;
    }


    //初始化
    for(int i = 0; i < N; i++)
    for(int j = 0; j < N; j++)
    {
        array[i][j] = 0;
    }

    constructArray(array,N);


    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            printf("%d ",array[i][j]);
        }
        printf("\n");
    }
    //內(nèi)存釋放
    for (int i = 0; i < N; i++)
    {
        free(array[i]);
    }
    free(array);

    return 0;
}