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 竟然都没发现。