算法学习之路|螺旋矩阵

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

输入格式：

输入在第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
解题思路：

将代码分为四个部分，

就用这个例子说，分为向下，向右，向上，向左。

第一次，98-53

第二次,58-60

第三次，76-81

第四次，93-95

然后依次类推，即可。

代码如下：

#include<iostream>
#include<algorithm>
#include<vector>
#include<stdio.h>
using namespace std;
int main(){
    int m=100000000,n=100000000,use;//m是行,n是列 m>=n
    int map[1000][1000]={0};
    
    cin>>use;
    
    for(int i=1;i<=use/2;i++){
        if(use%i==0&&m+n>use/i+i){
            m=max(i,use/i);
            n=min(i,use/i);
        }
    }
    vector<int> v;
    for(int i=0,tmp;i<use;i++){
        cin>>tmp;
        v.push_back(tmp);
    }
    sort(v.begin(),v.end());
    reverse(v.begin(),v.end());
    //===========
//    for(auto a:v)
//        cout<<a<<" ";
//    cout<<endl;
    //===========
    
    int i=0;
    int on=0,below=m-1,l=0,r=n-1;
    if(use==1){
        cout<<v[0];
        return 0;
    }
    else if(n==1){
        for(int i=0;i<use-1;i++)
            cout<<v[i]<<endl;
        cout<<v[use-1];
        return 0;
    }
    while(i<use){
        for(int j=l;j<=r;j++,i++)
            map[on][j]=v[i];
        on++;
        for(int j=on;j<=below;i++,j++)
            map[j][r]=v[i];
        r--;
        for(int j=r;j>=l;j--,i++)
            map[below][j]=v[i];
        below--;
        
        
        for(int j=below;j>=on;j--,i++)
            map[j][l]=v[i];
        l++;
    }
    for(int i=0;i<m-1;i++){
        for(int j=0;j<n-1;j++)
            printf("%d ",map[i][j]);
        cout<<map[i][n-1]<<endl;
    }
    for(int j=0;j<n-1;j++)
        printf("%d ",map[m-1][j]);
    cout<<map[m-1][n-1];
    
}