算法面试题二

输入n，生成一个n*n的矩阵，规定沿着45度方向递增，形成一个zigzag数组（JPEG编码里取像素数据的排列次序），请问如何实现？

例如：

实现如下：

void makeA(int **A,int N){
int sum=0;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
sum=i+j;
if(sum<N)
A[i][j]=sum*(sum+1)/2+(sum%2==0?j:i);
else{
A[i][j]=N*N-1-((N-1)*2-sum)*((N-1)*2-sum+1)/2-(((N-1)*2-sum)%2==0?(N-1-j):(N-1-i));
}
}
}
}

int main(int argc, char *argv[])
{ 
int N=9;
int **A;
int i;
A=(int **)malloc(sizeof(int *)*N);
for(i=0;i<N;i++)
*(A+i)=(int *)malloc(sizeof(int)*N);
makeA(A,N);
for(i=0;i<N;i++){
for(int j=0;j<N;j++){
cout<<setw(3)<<A[i][j]<<" ";
}
cout<<endl;
}
getchar();
for(i=0;i<N;i++)
        free(*(A+i));
        free(A);
return 0;
}