本题要求将给定的 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
思路：
本题较为简单，首先确定好矩阵的行列，由于要求m-n最小，因此我们从sqrt（N）向上查找，找到第一个能整除的整数就是m
int cal_m(int N)//计算矩阵的行数
{
int m;
m = int(sqrt(N));
if (m - sqrt(N)==0)return m;//首先要判断开方的数字是不是整数，如果是整数证明是一个正方形矩阵
else m++;
while (N % m != 0)
{
m++;
}
return m;
}
接下来我们将所有的数存储在数组中，通过sort进行排序
int N;
cin >> N;
int m = cal_m(N);
int n = N / m;
vector<int> store(N);
for (int i = 0; i<N; i++)//存储数据
{
cin >> store[i];
}
sort(store.begin(),store.end());
接下来我们需要定义四个边界，以及一个m*n的二维数组，通过下标i,j对这个矩阵进行螺旋填充
//这个是定义二维数组的方法
int **matrix=new int *[m];
for (int i = 0; i < m; i++)
{
matrix[i] = new int[n];
}
填充的时候按照右→下→左→上→右...的熟悉一直循环填充，直到下一次的填充达到边界为止退出
//定义四个边界以及i，j对矩阵进行填充，k来定位储存数据的位置
int up = -1, down = m, left = -1, right = n;//定义四个边界
int i = 0, j = 0, k = N-1;
while (1)
{
//----------------------向右填充----------------------------------------------
for (; j < right; j++)
{
matrix[i][j] = store[k];
k--;
}
up++;//向右填充完，上边界增加1
if (down == i + 1)break;//接下来向下填充，如果下边界只比i大1，证明填充完毕
else { i++; j--;}//否则将坐标移动到下一个要填充的位置
//---------------------向下填充-----------------------------------------------
for (; i < down; i++)
{
matrix[i][j] = store[k];
k--;
}
right--;//向下填充完，右边界减少1
if (left == j-1)break;//接下来向左填充，如果左边界只比j小1，证明填充完毕
else { j--; i--; }//否则将坐标移动到下一个要填充的位置
//---------------------向左填充-----------------------------------------------
for (; j > left; j--)
{
matrix[i][j] = store[k];
k--;
}
down--;//向左填充完，下边界减少1
if (up == i - 1)break;//接下来向上填充，如果上边界只比i小1，证明填充完毕
else {i--; j++;}//否则将坐标移动到下一个要填充的位置
//---------------------向上填充-----------------------------------------------
for (; i > up; i--)//向上填充
{
matrix[i][j] = store[k];
k--;
}
left++;//向上填充完，左边界增加1
if (right == j + 1)break;//接下来向右填充，如果右边界只比j大1，证明填充完毕
else { j++; i++; }//否则将坐标移动到下一个要填充的位置
}
填充完毕就输出就可以了：
for (i = 0; i < m; i++)
{
for (j = 0; j < n-1; j++)
{
cout << matrix[i][j] << ' ';
}
cout << matrix[i][j] << endl;
}
代码：
//1050 螺旋矩阵
#include<iostream>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
int cal_m(int N)//计算矩阵的行数
{
int m;
m = int(sqrt(N));
if (m - sqrt(N)==0)return m;
else m++;
while (N % m != 0)
{
m++;
}
return m;
}
int main()
{
int N;
cin >> N;
int m = cal_m(N);
int n = N / m;
vector<int> store(N);
for (int i = 0; i<N; i++)//存储数据
{
cin >> store[i];
}
sort(store.begin(),store.end());
//定义m*n的二维数组
int **matrix=new int *[m];
for (int i = 0; i < m; i++)
{
matrix[i] = new int[n];
}
//定义四个边界以及i，j对矩阵进行填充，k来定位储存数据的位置
int up = -1, down = m, left = -1, right = n;//定义四个边界
int i = 0, j = 0, k = N-1;
while (1)
{
//----------------------向右填充----------------------------------------------
for (; j < right; j++)
{
matrix[i][j] = store[k];
k--;
}
up++;//向右填充完，上边界增加1
if (down == i + 1)break;//接下来向下填充，如果下边界只比i大1，证明填充完毕
else { i++; j--;}//否则将坐标移动到下一个要填充的位置
//---------------------向下填充-----------------------------------------------
for (; i < down; i++)
{
matrix[i][j] = store[k];
k--;
}
right--;//向下填充完，右边界减少1
if (left == j-1)break;//接下来向左填充，如果左边界只比j小1，证明填充完毕
else { j--; i--; }//否则将坐标移动到下一个要填充的位置
//---------------------向左填充-----------------------------------------------
for (; j > left; j--)
{
matrix[i][j] = store[k];
k--;
}
down--;//向左填充完，下边界减少1
if (up == i - 1)break;//接下来向上填充，如果上边界只比i小1，证明填充完毕
else {i--; j++;}//否则将坐标移动到下一个要填充的位置
//---------------------向上填充-----------------------------------------------
for (; i > up; i--)//向上填充
{
matrix[i][j] = store[k];
k--;
}
left++;//向上填充完，左边界增加1
if (right == j + 1)break;//接下来向右填充，如果右边界只比j大1，证明填充完毕
else { j++; i++; }//否则将坐标移动到下一个要填充的位置
}
//输出结果
for (i = 0; i < m; i++)
{
for (j = 0; j < n-1; j++)
{
cout << matrix[i][j] << ' ';
}
cout << matrix[i][j] << endl;
}
return 0;
}
网友评论