This time your job is to fill a sequence of N positive integers into a spiral matrix in non-increasing order. A spiral matrix is filled in from the first element at the upper-left corner, then move in a clockwise spiral. The matrix has m rows and ncolumns, where m and n satisfy the following: m*n must be equal to N; m>=n; and m–n is the minimum of all the possible values.
Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N. Then the next line contains N positive integers to be filled into the spiral matrix. All the numbers are no more than 104. The numbers in a line are separated by spaces.
Output Specification:
For each test case, output the resulting matrix in m lines, each contains n numbers. There must be exactly 1 space between two adjacent numbers, and no extra space at the end of each line.
Sample Input:
|
1 2 |
12 37 76 20 98 76 42 53 95 60 81 58 93 |
Sample Output:
|
1 2 3 4 |
98 95 93 42 37 81 53 20 76 58 60 76 |
PAT-Basic-1050. 螺旋矩阵的英文版。
代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 |
#include<stdio.h> #include<stdlib.h> int *buf,**matrix,guide=0,m,n,N; struct position { int x; int y; } filler={0,0},direction[4]={{1,0},{0,1},{-1,0},{0,-1}}; int rcompare(const void *a,const void *b) { return *(int *)b-*(int *)a; } int canmove() { int x,y; x=filler.x+direction[guide].x; y=filler.y+direction[guide].y; if(x<0||x>=n||y<0||y>=m) { return 0; } else if(matrix[y][x]!=0) { return 0; } return 1; } int move(int count) { matrix[filler.y][filler.x]=buf[count]; if(count==N-1) { return 0; } while(!canmove()) { guide=(guide+1)%4; } filler.y+=direction[guide].y; filler.x+=direction[guide].x; return 0; } int main() { int i,j,count=0; scanf("%d",&N); buf=(int *)malloc(N*sizeof(int)); for(i=0;i<N;i++) { scanf("%d",buf+i); } qsort(buf,N,sizeof(int),rcompare); m=N; n=1; for(i=N;i>0;i--) { if(N%i==0) { if(i-N/i<0) { break; } if(i-N/i<m-n) { m=i; n=N/i; } } } matrix=(int **)malloc(m*sizeof(int *)); for(i=0;i<m;i++) { matrix[i]=(int *)calloc(n,sizeof(int)); } while(count<N) { move(count); count++; } for(i=0;i<m;i++) { for(j=0;j<n-1;j++) { printf("%d ",matrix[i][j]); } printf("%d\n",matrix[i][j]); } } |