PAT 甲级 刷题日记|A 1105 Spiral Matrix

单词积累

clockwise 顺时针方向的

spiral 螺旋的

思路

本质是模拟的思想，用i标记遍历到第几圈，然后分为矩形的四个边（对应下图不同颜色），分别去赋值，注意边界点即可。

此外，还有可能出现3 7这样的数字，数组为3*1，为了不让第四次的值覆盖第二次的值，此处选取的做法是判断值有没有赋完，赋完立刻退出。

代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 10002;
int N;
int m, n;
int num[maxn];
int ans[maxn][maxn];

bool cmp (int a, int b) {
    return a > b;
}

int main() {
    cin>>N;
    for (int i = 0; i < N; i++) {
        cin>>num[i];
    }
    sort(num, num + N, cmp);
    for (int i = sqrt(N); i >= 0; i--) {
        if (N % i == 0) {
            n = i;
            m = N / n;
            break;
        }
    }
    int indexs = 0;
    int cri = 0;
    if (n % 2 == 0) cri = n / 2;
    else cri = n / 2 + 1;
    for (int i = 0; i < cri; i++) {
        for (int j = i; j < n - i; j++) {
            ans[i][j] = num[indexs++];
//          cout<<1<<" "<<i<<" "<<j<<" "<<ans[i][j]<<endl;
        }
        if (indexs >= N) break;
        for (int j = i + 1; j < m - i; j++) {
            ans[j][n - i - 1] = num[indexs++];
//          cout<<2<<" "<<j<<" "<<n - i - 1<<" "<<ans[j][n - i - 1]<<endl;
        }
        if (indexs >= N) break;
        for (int j = n - i - 2; j >= i; j--) {
            ans[m - i - 1][j] = num[indexs++];
//          cout<<3<<" "<<m - i - 1<<" "<<j<<" "<<ans[m - i - 1][j]<<endl;
        }
        if (indexs >= N) break;
        for (int j = m - i - 2; j > i; j--) {
            ans[j][i] = num[indexs++];
//          cout<<4<<" "<<j<<" "<<i<<" "<<ans[j][i]<<endl;
        }
        if (indexs >= N) break;
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cout<<ans[i][j];
            if (j != n - 1) cout<<" ";
        }
        cout<<endl;
    }
    
}