1105. Spiral Matrix (25)
This time your job is to fill a sequence of N positive integers into a spiral matrix in non-increasing order. A spiral matrixis 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:12 37 76 20 98 76 42 53 95 60 81 58 93Sample Output:
98 95 93 42 37 81 53 20 76 58 60 76
思路
题目要求将N个数转换成 m*n 大小的矩阵形式，其中必须满足:
1.m*n = N且满足m-n最小（m >= n）
2.矩阵中的数按从大到小呈顺时针向内螺旋的形式排列，类似一个漩涡一样。
那么有：
1.先将这组数按递减排序。
2.暴力枚举找出满足题目要求1的m和n，构建矩阵二维数组
3.按照顺时针遍历矩阵，将数字一个个输入进去
4.输出。
注意：
1.构建矩阵时可以弄一堵"墙"保证遍历不越界，另外走过的地方也算"墙"(即matrix[i][j] != -1)。
2.用一个数组go[4]表示遍历的每一步（右下左上，顺时针），每当遇到墙（matrix[i][j] != -1,要么是INIT_MAX，要么是之前走过的地方）时改变方向，如此循环。
代码
#include<iostream>
#include<vector>
#include<math.h>
#include<algorithm>
using namespace std;
/*
1.排序
2.找m、n
3.构建矩阵
4.输出
*/
vector<vector<int>> go ={{0,1},{1,0},{0,-1},{-1,0}};//右下左上
const int INIT_MAX = pow(2,30);
bool cmp(const int a,const int b)
{
return a > b;
}
int main()
{
int N;
while(cin >> N)
{
vector<int> num(N);
for(int i = 0;i < N;i++)
{
cin >> num[i];
}
sort(num.begin(),num.end(),cmp);
//find min(m - n)
int m,n,curmin = INIT_MAX;
for(int i = N;i >= sqrt(N);i--)
{
if(i * (N/i) == N && i - (N/i) < curmin)
{
m = i;
n = N/i;
curmin = m - n;
}
}
//build matrix
vector<vector<int>> matrix(m + 2,vector<int>(n + 2,-1));
for(int i = 0;i <= n + 1;i++)
{
matrix[0][i] = matrix[m + 1][i] = INIT_MAX;
}
for(int i = 0;i <= m + 1;i++)
{
matrix[i][0] = matrix[i][n + 1] = INIT_MAX;
}
int a = 1,b = 1,dir = 0;
matrix[a][b] = num[0];
for(int i = 1;i < num.size();i++)
{
if(matrix[a+go[dir][0]][b+go[dir][1]] != -1)
{
dir++;
if(dir > 3)
dir = 0;
}
a += go[dir][0];
b += go[dir][1];
matrix[a][b] = num[i];
}
//output
for(int i = 1;i <= m;i++)
{
for(int j = 1;j <= n;j++)
{
if(j != 1)
cout << " ";
cout << matrix[i][j];
}
cout << endl;
}
}
}