1105 Spiral Matrix (25分)

比眉伴天荒 2023-07-10 08:58 4阅读 0赞

#### 题意： ####

第一行输入数据的个数n，然后输入n个数字，首先对n个数按从大到小顺序排序。最后输出的时候按照螺旋状输出。

#### 解题思路： ####

1.state记录当前填充方向，首先从右开始，按照右下左上的顺序，一直循环  
2.prerow,precolumn记录上一个位置的行和列数据  
3.在填充好一个数字以后，及时更新下一个位置的信息（prerow,precolumn）

#include<iostream>
    #include<algorithm>
    #include<cmath>
    using namespace std;
    int getm(int n)
    { 
        int i=sqrt(n);
        if(i*i==n)return i;
        for(i+=1;i<=n;i++)
        { 
            if(n%i==0)return i;
        }
    }
    bool cmp(int a,int b)
    { 
        return a>b;
    }
    int main()
    { 
        int nn;
        cin>>nn;
        int m,n;
        m=getm(nn);
        n=nn/m;
        int result[m+5][n+5];
        int input[nn+5];
        for(int i=0;i<m;i++)for(int j=0;j<n;j++) result[i][j]=-1;
        for(int i=0;i<nn;i++)cin>>input[i];
        sort(input,input+nn,cmp);
        int state=1;//记录当前状态，上下左右
        int prerow=0,precolumn=0,curi=0;//上一个位置的行和列
        while(nn--)
        { 
            result[prerow][precolumn]=input[curi++];//填充数字
            if(state%4==1)//当前方向是右
            { 
                if(result[prerow][precolumn+1]==-1)//判断当前位置是否有效
                { 
                    precolumn++;
                }
                else
                { 
                    state++;prerow++;
                }
            }
            else if(state%4==2)//当前方向是下
            { 
                if(result[prerow+1][precolumn]==-1)
                { 
                    prerow++;
                }
                else{ state++;precolumn--;}
            }
            else if(state%4==3)//左
            { 
                if(result[prerow][precolumn-1]==-1)
                precolumn--;
                else{ state++;prerow--;}
            }
            else//上
            { 
                if(result[prerow-1][precolumn]==-1)prerow--;
                else{ state++;precolumn++;}
            }    
        }
        for(int i=0;i<m;i++)
        { 
            for(int j=0;j<n;j++)
            { 
                cout<<result[i][j];
                if(j<n-1)cout<<" ";
                else cout<<endl;
            }
        }
        return 0;
    }