A1105 Spiral Matrix (25 point(s))

递归

1. 原文

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 mrows and n columns, 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 10^4. 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:

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

Sample output:

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

2. 解析

3. AC代码

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int num[10010]={};
bool cmp(int x,int y){
	return x>y;
}
int getnum(int x){
	int a=sqrt(1.0*x);
	while(a!=1){
		if (x%a==0)
		{
			break;
		}else{
			a--;
		}
	}
	return a;
}
int matrix[10010][10010];
int main()
{
	int N;
	scanf("%d",&N);
	for (int i = 0; i < N; ++i)
	{
		scanf("%d",&num[i]);
	}
	sort(num,num+N,cmp);
    int n=getnum(N);
    int m=N/n;
    int level=N/2+N%2;
    int t=0;
    for (int j = 0; j < level; ++j)
    {
    	for (int i = j; i < n-j&&t<N; ++i)
	    {
	    	matrix[j][i]=num[t++];
	    }
	    for (int i = 1+j; i < m-j&&t<N; ++i)
	    {
	    	matrix[i][n-1-j]=num[t++];
	    }
	    for (int i = n-2-j; i >= j&&t<N ; i--)
	    {
	    	matrix[m-1-j][i]=num[t++];
	    }
	    for (int i = m-2-j; i >= j+1&&t<N ; i--)
	    {
	    	matrix[i][j]=num[t++];
	    }
    }
    for (int i = 0; i < m; ++i)
    {
    	for (int j = 0; j < n; ++j)
    	{
    		if (j!=0)
    		{
    			printf(" ");
    		}
			printf("%d",matrix[i][j]);
    	}
    	printf("\n");
    }
	return 0;
}