PAT 1105. Spiral Matrix (25)

Posted on Edited on In

This time your job is to fill a sequence of N positive integers into a spiral matrix in non-increasing order. A spiral matrixis filled in from the first element at the upper-left corner, then move in a clockwise spiral. The matrix has m rows and ncolumns, where m and n satisfy the following: m*n must be equal to N; m>=n; and m-n is the minimum of all the possible values.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N. Then the next line contains N positive integers to be filled into the spiral matrix. All the numbers are no more than 104. The numbers in a line are separated by spaces.

Output Specification:

For each test case, output the resulting matrix in m lines, each contains n numbers. There must be exactly 1 space between two adjacent numbers, and no extra space at the end of each line.

Sample Input:

12
37 76 20 98 76 42 53 95 60 81 58 93

Sample Output:

98 95 93
42 37 81
53 20 76
58 60 76

模拟走的路径

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <cstdio>
#include <cmath>
#include <cstdlib>

int cmp(const void *a, const void *b) {
    int arg1 = *static_cast<const int *>(a);
    int arg2 = *static_cast<const int *>(b);

    if (arg1 < arg2) return -1;
    if (arg2 < arg1) return 1;
    return 0;
}

int main() {
    int N = 0;
    scanf("%d", &N);
    int n = sqrt(N);
    while (N % n != 0) {
        n--;
    }

    int *nums = new int[N];
    for (int i = 0; i < N; i++) {
        scanf("%d", &nums[i]);
    }
    qsort(nums, N, sizeof(nums[0]), cmp);

    int m = N / n;
    if (m < n) {
        int temp = m;
        m = n;
        n = temp;
    }
    int **spiral = new int *[m + 2];
    for (int i = 0; i <= m + 1; i++) {
        spiral[i] = new int[n + 2];
        spiral[i][0] = spiral[i][n + 1] = -1;
        if (i == 0 || i == m + 1) {
            for (int j = 1; j <= n; j++) {
                spiral[i][j] = -1;
            }
        } else {
            for (int j = 1; j <= n; j++) {
                spiral[i][j] = 0;
            }
        }
    }

    int i = 1, j = 0;
    while (N > 0) {
        while (spiral[i][j + 1] == 0) {
            j++;
            N--;
            spiral[i][j] = nums[N];
        }
        while (spiral[i + 1][j] == 0) {
            i++;
            N--;
            spiral[i][j] = nums[N];
        }
        while (spiral[i][j - 1] == 0) {
            j--;
            N--;
            spiral[i][j] = nums[N];
        }
        while (spiral[i - 1][j] == 0) {
            i--;
            N--;
            spiral[i][j] = nums[N];
        }
    }

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (j == 1) printf("%d", spiral[i][1]);
            else printf(" %d", spiral[i][j]);
        }
        printf("\n");
    }

    for (int i = 0; i <= m + 1; i++) {
        delete[] spiral[i];
    }
    delete[] spiral;
    delete[] nums;

    return 0;
}