1105 spiral matrix (25 points)

1105 Spiral Matrix (25 branch )

The question

Give a group N Number , Put this N Fill in one number m*n In the spiral matrix . The spiral matrix is monotonically non increasing from the outer circle to the most central circle . The first number is in the upper left corner of the outermost circle . and m * n = N,m>=n And m And n It should be the group with the smallest difference among all the requirements m,n.

input
12
37 76 20 98 76 42 53 95 60 81 58 93

output

98 95 93
42 37 81
53 20 76
58 60 76

Ideas

A slightly troublesome simulation problem . It's easy to think , Find the one that meets the requirements first m,n, And sort this group of numbers from large to small , Then simulate the spiral matrix and fill in the numbers in turn .
look for m,n. It's easy to know ,n Must be less than or equal to N prescribing . from N Find the formula of , The first one is divisible N The number of is n,m be equal to N/n.

call sort Sort the sequence

The spiral matrix starts from the first to the right , And then down , Then to the left , Then go up , To the right …
It's easy to find patterns ：
In the direction of ： Right down Down to the left Left to top Up to right
When they encounter obstacles, they will change direction （ Out of matrix range , Hit the position where the number has been filled ）

problem

The general idea of a simulation question is very simple , But there are many details . Maybe one condition is wrong, and the final result is far worse . Note the various boundaries and coordinates .

Code

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>

using namespace std;

int N, list[10007];

bool cmp(int a, int b){
	return a>b;
}

int factor(int N){		// return n
	int n;
	n=sqrt(N);
	for(int i=n; i>=1; i--){
		if(N%i == 0){
			return i;
		}
	}
}

void matr(){
	int mat[107][107], vis[107][107], x=0, y=0, m, n;
	int direc[2]={0,1};
	memset(vis,0,sizeof(vis));
	n=factor(N);
	m=N/n;
	mat[0][0]=list[0];
	vis[0][0]=1;
	for(int i=1; i<N; i++){
		if(x+direc[1]<n&&x+direc[1]>=0&&y+direc[0]<m&&y+direc[0]>=0&&vis[y+direc[0]][x+direc[1]]==0){
			y+=direc[0];
			x+=direc[1];
			mat[y][x]=list[i];
			vis[y][x]=1;
//			printf("mat[%d][%d] = %d\n",y,x,mat[y][x]);
		}else{
			if(direc[0]==0){
				if(direc[1]==1){
					direc[0]=-1;
					direc[1]=0;
//					printf("right to down\n");
				}else{
					direc[0]=1;
					direc[1]=0;
//					printf("left to up\n");
				}
			}else if(direc[0]==-1){
				direc[0]=0;
				direc[1]=-1;
//				printf("down to left\n");
			}else if(direc[0]==1){
				direc[0]=0;
				direc[1]=1;
//				printf("up to right\n");
			}
			i-=1;
//			printf("i= %d\n",i);
		}
	}
	
	for(int i=0; i<m; i++){
		if(i!=0){
			printf("\n");
		}
		for(int j=0; j<n; j++){
			if(j!=0){
				printf(" ");
			}
			printf("%d",mat[i][j]);
		}
	}
}
int main()
{

//	int list[10007];
	scanf("%d",&N);
	for(int i=0; i<N; i++){
		scanf("%d",&list[i]);
	}
	sort(list, list+N,cmp);
//	for(int i=0;i<N;i++){
//		printf("%d ",list[i]);
//	}
//	printf("\n");
	matr();
	return 0;
}