Home PAT 1105 Spiral Matrix
Post
Cancel

PAT 1105 Spiral Matrix

Link

AC 代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <cmath>
using namespace std;
int N,m,n;
int main() {
    scanf("%d",&N);
    for(int i=sqrt(N);i>=1;--i)
        if(N%i==0){
            m=N/i,n=i;
            break;
        }
    vector<vector<int>>b(m+1);
    for(int i=1;i<=m;++i)
        b[i].resize(n+1);
    vector<int>a(N);
    for(int i=0;i<N;++i)
        scanf("%d",&a[i]);
    sort(a.begin(),a.end(),greater<int>());
    int index=0;
    int left=1,right=n,top=1,bottom=m;
    while(left<=right&&top<=bottom){
        for(int i=left;i<=right;++i)
            b[top][i]=a[index++];
        for(int i=top+1;i<bottom;++i)
            b[i][right]=a[index++];
        for(int i=right;i>=left;--i){
            if(top==bottom) break;
            b[bottom][i]=a[index++];
        }
        for(int i=bottom-1;i>top;--i){
            if(left==right) break;
            b[i][left]=a[index++];
        }
        left++,right--,top++,bottom--;
    }
    for(int i=1;i<=m;++i){
        for(int j=1;j<=n;++j){
            if(j!=1) printf(" ");
            printf("%d",b[i][j]);
        }
        printf("\n");
    }
    return 0;
}
This post is licensed under CC BY 4.0 by the author.