1105. Spiral Matrix(25)[시뮬레이션] - PAT(Advanced Level) Practise

제목 정보

1105. Spiral Matrix (25)
시간 제한 150ms 메모리 제한 65536kB 코드 길이 제한 16000 B This time your job is to fill a sequence of N positive integers into a spiral matrix in non-increasing order.A spiral matrix is filled in from the first element at the upper-left corner, then move in a clockwise spiral. The matrix has m rows and n columns, 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 10^4. 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

문제풀이의 방향

검색 시뮬레이션

AC 코드

#include 
#include 
#include 
#include 
#include 
using namespace std;
vector<vector<int> > mp;
vector<int> v;
int T, t, m, n;
int dir[4][2] = {1, 0, 0, -1, -1, 0, 0, 1};
int did = 0;
void fill(int x, int y, int p){
    while (p < v.size()){
        mp[y][x] = v[p++];
        if (mp[y + dir[did][1]][x + dir[did][0]] > 0){
            did = (did + 1)%4;
        }
        x += dir[did][0];
        y += dir[did][1];
    }
}
int main()
{
    int T, t;
    scanf("%d", &T);
    for (int i = 0; i < T; ++i){
        scanf("%d", &t);
        v.push_back(t);
    }
    sort(v.begin(), v.end(), greater<int>());
    n = (int)sqrt(T);
    while (n > 1 && T%n != 0){
        --n;
    }

    m = T/n;
    mp.resize(m + 2);
    for (int i = 0; i < m + 2; ++i){
        if (i == 0 || i == m + 1){
            mp[i].assign(n + 2, 1);
        }else{
            mp[i].assign(n + 2, 0);
        }
        mp[i][0] = mp[i][n + 1] = 1;
    }
    fill(1, m, 0);
    for (int i = m; i >= 1; --i){
        printf("%d", mp[i][1]);
        for (int j = 2; j <= n; ++j){
            printf(" %d", mp[i][j]);
        }
        printf("
");
    }
    return 0;
}