1105 Spiral Matrix （25 分)

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 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

作者: CHEN, Yue

单位: 浙江大学

时间限制: 200 ms

内存限制: 64 MB

代码长度限制: 16 KB

题目大意

将一个数组由大到小排成一个螺旋数组。其中矩阵行与列的差要最小。

分析

首先计算出m,n，肯定大约是根号N的。从根号N开始，m逐渐增加，找到第一个n。如果n大于m，则交换。

然后用dir变量控制填入矩阵的方向。

代码

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <deque>
#include <queue>
#include <map>
#include <set>
#include <cstring>
#include <cmath>
#include <sstream>

using namespace std;
int t, m, n;
vector<int> num;
vector<vector<int>> matrix;
int dirt[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int main() {
    cin >> t;
    m = sqrt(t);
    for (; m <= t; m++)
        if (t % m == 0) {
            n = t / m;
            break;
        }
    if (n > m)//防止出现m=4,n=5这种情况
        swap(n, m);
    matrix.resize(m);
    for(int i=0;i<m;i++)
        matrix[i].resize(n);
    num.resize(t);
    for (int i = 0; i < t; i++)
        cin>>num[i];
    sort(num.begin(),num.end(),greater<int>());

    int cnt=0,dir=0,x=0,y=0;
    while(cnt<t){
        matrix[x][y]=num[cnt++];
        if((dir==0&&y==n-1)||(dir==0&&matrix[x][y+1]!=0))//向右到头，转下
            dir=1;
        else if((dir==1&&x==m-1)||(dir==1&&matrix[x+1][y]!=0))//向下到头，转左
            dir=2;
        else if((dir==2&&y==0)||(dir==2&&matrix[x][y-1]!=0))//向左到头，转上
            dir=3;
        else if((dir==3&&x==0)||(dir==3&&matrix[x-1][y]!=0))//向上到头，转右
            dir=0;
        x+=dirt[dir][0];
        y+=dirt[dir][1];
    }
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(j!=0)
                cout<<" ";
            cout<<matrix[i][j];
        }
        cout<<endl;
    }
    return 0;
}