【PAT】1105 Spiral Matrix（柳婼的思想详细解读）

【PAT】1105 Spiral Matrix

用的就是是柳大姐的思想：柳姐传送门
先计算行数m和列数n的值，n从根号N的整数部分开始，往前推一直到1，找到第一个满足N % n== 0的，m的值等于N/n～将N个给定的值输入数组a，并将a数组中的值按非递增排序，接着建立m行n列的数组b，填充时按层数填充，一个包裹矩阵的口字型为一层，计算螺旋矩阵的层数level，如果m的值为偶数，层数为m/2，如果m为奇数，层数为m/2+1，所以level = m / 2 + m % 2；因为是从左上角第1个格子开始，按顺时针螺旋方向填充，所以外层for循环控制层数i从0到level，内层for循环按左上到右上、右上到右下、右下到左下、左下到左上的顺序一层层填充，注意内层for循环中还要控制t <= N – 1，因为如果螺旋矩阵中所有的元素已经都填充完毕，就不能再重复填充～填充完毕后，输出整个矩阵～

下面以一个5*4的矩阵为例：（m=5,n=4）

可以看到每一层都需要分为四个步骤进行填充数字。若将元素的下标看成是一个x,y的坐标，我们很容易就可以总结出①②③④遍历过程中x,y的取值范围。其中i表示正在填充第i层，从0开始。

① x:i              y:i ~ n-i-1
② x:i+1 ~ m-i-2    y:n-i-1
③ x:m-1-i          y:n-i-1 ~ i
④ x:m-i-2 ~ i+1    y: i

在每一轮循环遍历的过程中，我们还需要进行 cnt <= N - 1 的判断（否则会有测试点通不过，例如：只有19个元素，13个元素的时候，大家可以试一试）。其中cnt表示已经填充元素的个数，而N表示元素总个数。

AC代码：

#include<bits/stdc++.h>
using namespace std;
vector<int> v;
int cmp(int a, int b) {
	return a > b;
}
int main() {
	int N,m,n; scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		int temp; scanf("%d", &temp);
		v.push_back(temp);
	}
	sort(v.begin(), v.end(), cmp);
	n = (int)sqrt(N);
	while (N%n) n++;//N%n==0时退出循环
	m = N / n;
	if (m < n) swap(n, m);//保持m>=n;
	vector<vector<int> > ans(m, vector<int>(n));
	int level = n / 2 + n % 2;//计算一共有几层。
	int cnt = 0;//记录当前数组的下标
	for (int i = 0; i < level; i++) {//此时开始遍历每一层
		for (int j = i; j < n - i && cnt <= N - 1; j++)//①
			ans[i][j] = v[cnt++];
		for (int j = i + 1; j < m - i - 1 && cnt <= N - 1; j++) //②
			ans[j][n - 1 - i] = v[cnt++];
		for (int j = n - i - 1; j >= i && cnt <= N - 1; j--)//③
			ans[m - i - 1][j] = v[cnt++];
		for (int j = m - i - 2; j >= i + 1 && cnt <= N - 1; j--)//④
			ans[j][i] = v[cnt++];
	}
	for (int i = 0; i < m; i++) {
		cout << ans[i][0];
		for (int j = 1; j < n; j++) {
			cout<<" "<< ans[i][j];
		}
		cout << endl;
	}
}