算法面试题二

输入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;
}