题目

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

输入格式：

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

输出格式：

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

输入样例：

1
2

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

输出样例：

1
2
3
4

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

思路

  • 确定m和n：m是大于sqrt(N)且能整除N的最小整数，故只需m从1递增，直到满足m * m >= N && N % m == 0，即可找到m，然后n = N / m。

  • 填充旋转矩阵： 这个估计很难直接找出通项公式，所以一般的方法都是乖乖地一圈一圈地赋值。那么关键就是 如何控制坐标实现在矩阵里“螺旋地”遍历 ，这里总结一下我看到的方法中代表性的几个：

    • （递减法）我用的方法，每次（螺旋地向内）填充一个边，长度依次递减：n，m-1，n-1，m-2，n-2，m-3，……，直到长度到0；
    • （矩形法）一圈一圈的填，每次通过矩形四边的坐标确定边界，如 http://www.liuchuo.net/archives/2070 ；
    • （碰壁法）每次到达矩阵外部或者已经填过的，便变化方向，如 http://www.cnblogs.com/zhien-aa/p/5671115.html ， http://blog.csdn.net/luoluozlb/article/details/51567610 。并且后者使用两个int[4]数组代表4个方向的做法很棒，能使代码减少重复。

为什么我感觉找到的三篇都是女生的(・∀・(・∀・(・∀・*)

代码

Github最新代码，欢迎交流

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

#include <stdio.h>
#include <stdlib.h>

int cmp(const void *a, const void *b)
{
	return *(int*)b - *(int*)a;
}

int main()
{
	int N, m, n;
	int array[10000] = {0}, matrix[10000] = {0};

	scanf("%d", &N);
	for (int i = 0; i < N; i++)
		scanf("%d", array + i);

	qsort(array, N, sizeof(int), cmp);

	/* determine m and n */
	for (m = 1; !(m * m >= N && N % m == 0); m++) ;
	n = N / m;

	int x = -1, y = 0, index = 0;
	int horizontal = n, virtical = m;

	while (horizontal > 0 && virtical > 0) {
		for (int i = 0; i < horizontal && virtical > 0; i++)  /* toward right */
			matrix[y * n + ++x] = array[index++];
		virtical--;

		for (int i = 0; i < virtical && horizontal > 0; i++)  /* toward bottom */
			matrix[++y * n + x] = array[index++];
		horizontal--;

		for (int i = 0; i < horizontal && virtical > 0; i++)  /* toward left */
			matrix[y * n + --x] = array[index++];
		virtical--;

		for (int i = 0; i < virtical && horizontal > 0; i++)  /* toward top */
			matrix[--y * n + x] = array[index++];
		horizontal--;
	}

	for (int i = 0; i < m; i++)
		for (int j = 0; j < n; j++)
			printf("%d%c", matrix[i * n + j], j == n - 1 ? '\n' : ' ');

	return 0;
}