|
本题要求将给定的 N 个正整数按非递增的顺序，填入“螺旋矩阵”。所谓“螺旋矩阵”，是指从左上角第 1 个格子开始，按顺时针螺旋方向填充。要求矩阵的规模为 m 行 n 列，满足条件：m×n 等于 N；m≥n；且 mn 取所有可能值中的最小值。
输入格式：
输入在第 1 行中给出一个正整数 N，第 2 行给出 N 个待填充的正整数。所有数字不超过 104，相邻数字以空格分隔。
输出格式：
输出螺旋矩阵。每行 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
本题是要按螺旋的顺序来为一个空二维矩阵的每个位置填充数字，与这种规律类似的还有Z字型填充，就像下图这样：
这种题我总结了一种通用做法，就是假设有一个指针在指引着填充数字的位置，然后找出这个指针的所有运动方向。在本题中这个指针有四个运动方向，即上下左右，不同状态下矩阵的两个下标的变化不同。假设这个二维矩阵的两个下标为i和j。则分析螺旋的四种状态下的变化：
上：在同一列运动，j不变，i减1。若走到头则转为右
下：在同一列运动，j不变，i加1。若走到头则转为左
左：在同一行运动，i不变，j减1。若走到头则转为下
右：在同一行运动，i不变，j加1。若走到头则转为上
走到头包括两种情况，一种是到了矩阵的边界，再前进则越界，另一种是下一个位置已经有数字了。走到头后就应该变换前进方向。找出运动的规律之后依次填入数字，代码如下：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int N;
cin>>N;
int num[N];
for(int i=0;i<N;i++)
scanf("%d",&num[i]);
sort(num,num+N);
int n=(int)sqrt(N),m;//计算矩阵的行和列
while(N%n!=0)
n--;
m=N/n;
int res[m][n],i=0,j=0,flag=1;//i和j代表下标，flag表示前进方向
memset(res,0,sizeof(res));
for(int k=N-1;k>=0;k--)//要以非递增顺序填充，则排序后倒着遍历
{
if(flag==1)//向右
{
res[i][j]=num[k];
j++;
if(j==n || res[i][j]!=0)//走到头要转为向下，因为此时的下标是越界的，所以要纠正
{
j--;
i++;
flag=2;
}
}
else if(flag==2)//向下
{
res[i][j]=num[k];
i++;
if(i==m || res[i][j]!=0)//转为向左，并纠正坐标
{
j--;
i--;
flag=3;
}
}
else if(flag==3)//向左
{
res[i][j]=num[k];
j--;
if(j==-1 || res[i][j]!=0)//转为向上，纠正坐标
{
j++;
i--;
flag=4;
}
}
else//向上
{
res[i][j]=num[k];
i--;
if(i==-1 || res[i][j]!=0)//转为向右，纠正坐标
{
i++;
j++;
flag=1;
}
}
}
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
cout<<res[i][j];
if(j!=n-1)
cout<<" ";
}
cout<<endl;
}
return 0;
}
| 
转播
