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 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 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:
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
#include<stdio.h>
#include<algorithm>
using namespace std;
int seq[10005];
bool seqbool[105][105];
int out[105][105];
bool cmp(int a,int b)
{
return a>b;
}
int main()
{
int num;
scanf("%d",&num);
for(int i=0;i<num;i++)
{
scanf("%d",&seq[i]);
}
sort(seq,seq+num,cmp);
int min=num;
int m=num;
int n=1;
for(int i=1;i<=num;i++) //i为行
{
if(num%i==0)
{
int j=num/i;
if(i>=j&&((i-j)<=min))
{
m=i;
n=j;
min=i-j;
}
}
}
int tempm=0;
int tempn=0;
int i=0;
int prority=1;
while(1)
{
if(seqbool[tempm][tempn]!=true)
{
out[tempm][tempn]=seq[i];
i++;
seqbool[tempm][tempn]=true;
}
else
{
if(tempn!=n-1&&seqbool[tempm][tempn+1]==false)
{
if(prority!=1)
{
if(prority==2)
{
if(tempm!=m-1&&seqbool[tempm+1][tempn]==false)
{
tempm++;
prority==2;
}
else
{
tempn++;
prority=1;
}
}
if(prority==3)
{
if(tempn!=0&&seqbool[tempm][tempn-1]==false)
{
tempn--;
prority=3;
}
else
{
tempn++;
prority=1;
}
}
if(prority==4)
{
if(tempm!=0&&seqbool[tempm-1][tempn]==false)
{
tempm--;
prority=4;
}
else
{
tempn++;
prority=1;
}
}
}
else
{
tempn++;
prority=1;
}
}
else if(tempm!=m-1&&seqbool[tempm+1][tempn]==false)
{
if(prority!=2)
{
if(prority==1)
{
if(tempn!=n-1&&seqbool[tempm][tempn+1]==false)
{
tempn++;
prority=1;
}
else
{
tempm++;
prority=2;
}
}
if(prority==3)
{
if(tempn!=0&&seqbool[tempm][tempn-1]==false)
{
tempn--;
prority=3;
}
else
{
tempm++;
prority=2;
}
}
if(prority==4)
{
if(tempm!=0&&seqbool[tempm-1][tempn]==false)
{
tempm--;
prority=4;
}
else
{
tempm++;
prority=2;
}
}
}
else
{
tempm++;
prority=2;
}
}
else if(tempn!=0&&seqbool[tempm][tempn-1]==false)
{
tempn--;
prority=3;
}
else if(tempm!=0&&seqbool[tempm-1][tempn]==false)
{
tempm--;
prority=4;
}
}
if(i==num) break;
}
for(int t=0;t<m;t++)
{
for(int j=0;j<n;j++)
{
printf("%d",out[t][j]);
if(j!=n-1) printf(" ");
}
if(t!=m-1) printf("\n");
}
}