PAT_甲级_1105 Spiral Matrix

乔梓鑫 发布于 2 月 28 日

题目大意

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

算法思路

此题的求解步骤分为求解矩阵规模和填充矩阵

这里采用设置矩阵的4个边界(左右上下),分别为$left=0,right=col-1,up=0,bottom=row-1$，按照从左到右，从上到下，从右到左，从下到上的顺序依次填充，每一次填充完毕就更新边界，比如按照从左往右填充了一行就更新上边界up(++up)，只要每次填充完毕后,index>=n，说明填充结束。

提交结果

AC代码

#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    int a[n];
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
    }
    sort(a, a + n, [&](int a, int b) {
        return a > b;
    });
    // 计算m和n
    int col = (int) sqrt(n * 1.0);
    while (n % col != 0) {
        --col;
    }
    int row = n / col;
    int result[row][col];
    int index = 0;// 标记当前填充的元素
    // 定义数组的左右上下边界
    int left = 0, right = col - 1, up = 0, bottom = row - 1;
    while (index < n) {
        // 从左到右
        for (int i = left; i <= right; ++i) {
            result[up][i] = a[index++];
        }
        // 更新上界
        ++up;
        if (index >= n) break;
        // 从上到下
        for (int i = up; i <= bottom; ++i) {
            result[i][right] = a[index++];
        }
        // 更新右边界
        --right;
        if (index >= n) break;
        // 从右到左
        for (int i = right; i >= left; --i) {
            result[bottom][i] = a[index++];
        }
        // 更新下界
        --bottom;
        if (index >= n) break;
        // 从下到上
        for (int i = bottom; i >= up; --i) {
            result[i][left] = a[index++];
        }
        // 更新左边界
        ++left;
    }
    for (int i = 0; i < row; ++i) {
        for (int j = 0; j < col; ++j) {
            printf("%d", result[i][j]);
            if (j < col - 1) printf(" ");
        }
        printf("\n");
    }
    return 0;
}

PAT题解

关注专栏