本题要求将给定的N个正整数按非递增的顺序,填入“螺旋矩阵”。所谓“螺旋矩阵”,是指从左上角第1个格子开始,按顺时针螺旋方向填充。要求矩阵的规模为m行n列,满足条件:m*n等于N;m>=n;且m-n取所有可能值中的最小值。
输入格式:
输入在第1行中给出一个正整数N,第2行给出N个待填充的正整数。所有数字不超过104,相邻数字以空格分隔。
输出格式:
输出螺旋矩阵。每行n个数字,共m行。相邻数字以1个空格分隔,行末不得有多余空格。
输入样例:
1 2 |
12 37 76 20 98 76 42 53 95 60 81 58 93 |
输出样例:
1 2 3 4 |
98 95 93 42 37 81 53 20 76 58 60 76 |
尽管是一道25分的题,但是还算是比较简单的,一开始没想到这种相对简单的方法,打算通过一个变量level来控制螺旋的层数,实现顺时针螺旋遍历。
但是觉得这样太麻烦,刚打完这个变量名就想起了上学期C专题写的迷宫程序,当时用DFS生成迷宫时将 srand(time(NULL)) 放到了循环体内,就生成了一个螺旋的路线XD
于是,便又一次使用了类似于遍历迷宫的方法实现了这个矩阵的遍历。
代码如下:
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]); } } |
大神 ~我刚刚学习C;canmove和move那部分没有看懂 怎么实现自动选择方向的?filter作用是什么呢?
canmove 用于判断边界条件和是否访问过该位置,filler 用于记录当前所在位置的坐标,自动方向选择通过 direction 数组实现,在“遇到障碍物”前保持一个方向移动,否则改变为另一个方向。