1105 Spiral Matrix

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

题意

给定一个包含 N 个正整数的序列，需要我们将元素按照降序的填充到螺旋矩阵中。

从左上角第一个元素 ，顺时针进行填充。

另外，螺旋矩阵的行数 m 和列数 n 有如下要求：

m × n = N

m ≥ n

m - n 尽可能小

思路

具体思路如下：

1.先将给定的元素放入数组 w 中，并按照降序进行排序。

2.计算行数与列数，题目数据量不大，可以直接枚举求得。

3.按逆时针方向将元素填入螺旋矩阵，并输出最终结果。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 10010;
int w[N];
int main()
{
    //输入元素值
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)    cin >> w[i];
    //将元素按照降序排序
    sort(w, w + n, greater<int>());
    //计算符合题意的行列数
    int r, c;
    for (int i = 1; i <= n / i; i++)
        if (n % i == 0)
        {
            r = n / i;
            c = i;
        }
    //按题意往数组中填入元素
    vector<vector<int>> res(r, vector<int>(c));
    int dx[] = { -1,0,1,0 }, dy[] = { 0,1,0,-1 };
    for (int i = 0, x = 0, y = 0, d = 1; i < n; i++)
    {
        res[x][y] = w[i];
        int a = x + dx[d], b = y + dy[d];
        if (a < 0 || a >= r || b < 0 || b >= c || res[a][b])
        {
            d = (d + 1) % 4;
            a = x + dx[d], b = y + dy[d];
        }
        x = a, y = b;
    }
    //输出结果
    for (int i = 0; i < r; i++)
    {
        cout << res[i][0];
        for (int j = 1; j < c; j++)
            cout << " " << res[i][j];
        cout << endl;
    }
    return 0;
}