1050. 螺旋矩阵(25)

发表于 | 分类于 ，

题目描述

本题要求将给定的N个正整数按非递增的顺序，填入“螺旋矩阵”。所谓“螺旋矩阵”，是指从左上角第1个格子开始，按顺时针螺旋方向填充。要求矩阵的规模为m行n列，满足条件：m*n等于N；m>=n；且m-n取所有可能值中的最小值。

输入格式：

输入在第1行中给出一个正整数N，第2行给出N个待填充的正整数。所有数字不超过10^4^，相邻数字以空格分隔。

输出格式：

输出螺旋矩阵。每行n个数字，共m行。相邻数字以1个空格分隔，行末不得有多余空格。

输入样例：

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

输出样例：

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

提交代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;

int factorize(int N)
{
    int n = sqrt(N);
    do {
        if (N % n == 0) {
            return n;
        }
    } while (n--);
    return 1;
}

int main()
{
    int N, m, n;
    int spiral, idx;
    int i, j;
    vector<int> raw;
    vector<vector<int> > matrix;

    scanf("%d", &N);
    n = factorize(N);
    m = N / n;
    raw.resize(N);
    for (i = 0; i < N; i++) {
        scanf("%d", &raw[i]);
    }
    sort(raw.rbegin(), raw.rend());
    matrix.resize(m, vector<int>(n));

    spiral = m / 2 + m % 2;
    idx = 0;
    for (i = 0; i < spiral; i++) {
        for (j = i; j < n - i && idx < N; j++) {
            matrix[i][j] = raw[idx++];
        }
        for (j = i + 1; j < m - i - 1&& idx < N; j++) {
            matrix[j][n - i - 1] = raw[idx++];
        }
        for (j = i; j < n - i - 1 && idx < N; j++) {
            matrix[m - i - 1][n - j - 1] = raw[idx++];
        }
        for (j = i; j < m - i - 1 && idx < N; j++) {
            matrix[m - j - 1][i] = raw[idx++];
        }
    }

    for (i = 0; i < m; i++) {
        for (j = 0; j < n; j++) {
            if (j != 0) {
                printf(" ");
            }
            printf("%d", matrix[i][j]);
            if (j == n - 1) {
                printf("\n");
            }
        }
    }
    return 0;
}

个人思考

印象中大一程序设计期末考试就有一道螺旋矩阵的题目，不过稍微简单一点，只是要求稍简单一点，就是一个方阵，然后按顺序填 1, 2, 3, 4, 5, ... 不过当时没做出来。

其实这道题不难，主要问题是要抠细节（循环的边界条件），特别是加一减一的区别，还有就是要 idx < N 的判别条件，不然可能会把前面填的数字给覆盖掉。另外，还是要做足够充分的测试再提交吧，前几次提交的时候，内循环里面的 m 都写成了 n 竟然都没发现。