我的PAT系列文章更新重心已移至Github宽堆，歡迎來看PAT題解的小伙伴請到Github Pages瀏覽最新內(nèi)容恨狈。此處文章目前已更新至與Github Pages同步妆棒。歡迎star我的repo幻锁。
題目
本題要求將給定的 個(gè)正整數(shù)按非遞增的順序川抡，填入“螺旋矩陣”辐真。所謂“螺旋矩陣”，是指從左上角第 1 個(gè)格子開始崖堤，按順時(shí)針螺旋方向填充侍咱。要求矩陣的規(guī)模為
行
列，滿足條件：
等于
密幔；
楔脯；且
取所有可能值中的最小值。
輸入格式：
輸入在第 1 行中給出一個(gè)正整數(shù) 老玛，第 2 行給出
個(gè)待填充的正整數(shù)淤年。所有數(shù)字不超過
，相鄰數(shù)字以空格分隔蜡豹。
輸出格式：
輸出螺旋矩陣麸粮。每行 個(gè)數(shù)字，共
行镜廉。相鄰數(shù)字以 1 個(gè)空格分隔弄诲，行末不得有多余空格。
輸入樣例：
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
思路
確定m和n：m是大于sqrt(N)且能整除N的最小整數(shù)娇唯，故只需m從1遞增齐遵，直到滿足m * m >= N && N % m == 0，即可找到m塔插，然后n = N / m梗摇。
填充旋轉(zhuǎn)矩陣： 這個(gè)估計(jì)很難直接找出通項(xiàng)公式，所以一般的方法都是乖乖地一圈一圈地賦值想许。那么關(guān)鍵就是 如何控制坐標(biāo)實(shí)現(xiàn)在矩陣?yán)铩奥菪亍北闅v 伶授，這里總結(jié)一下我看到的方法中代表性的幾個(gè)：
（遞減法）我用的方法，每次（螺旋地向內(nèi)）填充一個(gè)邊流纹，長度依次遞減：n糜烹，m-1，n-1漱凝，m-2疮蹦，n-2，m-3茸炒，……愕乎，直到長度到0阵苇；
（矩形法）一圈一圈的填，每次通過矩形四邊的坐標(biāo)確定邊界妆毕，如
http://www.liuchuo.net/archives/2070 慎玖；（碰壁法）每次到達(dá)矩陣外部或者已經(jīng)填過的，便變化方向笛粘，如
http://www.cnblogs.com/zhien-aa/p/5671115.html 趁怔，
http://blog.csdn.net/luoluozlb/article/details/51567610 。并且后者使用兩個(gè)int[4]數(shù)組代表4個(gè)方向的做法很棒薪前，能使代碼減少重復(fù)润努。
為什么我感覺找到的三篇都是女生的(???(???(???*)
代碼
最新代碼@github，歡迎交流
#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;
}
