PAT 乙级 1050. 螺旋矩阵(25) C++版

本题要求将给定的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

首先需要确定m和n，根据题目已知的关于m和n的条件，可以通过程序计算出m和n的值，下面代码的setMAndN就是一个求解m和n的过程。在求解出m和n之后，就可以创建一个m行n列的矩阵了。函数fillMatrix以顺时针的方式，将已排序的数组填入到矩阵中。最后printMatrix打印出数组。

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

using namespace std;

int m = 1, n = 1, **matrix, *a;

void setMAndN(int N) {
    int min = 100001;
    // i is n
    for (int i = 1; i <= sqrt(N); i++) {
        if (N % i == 0) {
            // j is m
            int j = N / i;
            // m - n is the most small.
            if (min > j - i) {
                m = j;
                n = i;
                min = m - n;
            }
        }
    }
}

void setMatrix() {
    matrix = new int *[m];
    for (int i = 0; i < m; i++) {
        matrix[i] = new int[n];
    }
}

void fillMatrix(int N) {
    int index = N - 1;
    int i = 0, j = 0;
    while (index >= 0) {
        // right.
        for (; index >= 0 && j < n && matrix[i][j] == 0; j++) {
            matrix[i][j] = a[index--];
        }
        i++;
        j--;
        // down.
        for (; index >= 0 && i < m && matrix[i][j] == 0; i++) {
            matrix[i][j] = a[index--];
        }
        i--;
        j--;

        // left.
        for (; index >= 0 && j >= 0 && matrix[i][j] == 0; j--) {
            matrix[i][j] = a[index--];
        }
        i--;
        j++;

        // up.
        for (; index >= 0 && i >= 0 && matrix[i][j] == 0; i--) {
            matrix[i][j] = a[index--];
        }
        i++;
        j++;
    }
}

void printMatrix() {
    for (int i = 0; i < m; i++) {
        cout << matrix[i][0];
        for (int j = 1; j < n; j++) {
            cout << " " << matrix[i][j];
        }
        cout << endl;
    }
}

void release(int *a) {
    delete[] a;
    for (int i = 0; i < m; i++) {
        delete[] matrix[i];
    }
    delete[] matrix;
}

int main() {
    int N = 0;
    cin >> N;
    a = new int[N];
    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }

    sort(a, a + N);

    setMAndN(N);

    setMatrix();
    fillMatrix(N);
    printMatrix();
    release(a);
    return 0;
}