(PAT 1105) Spiral Matrix (WQNMD坑爹模拟题系列）-蒲公英云

(PAT 1105) Spiral Matrix (WQNMD坑爹模拟题系列）

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 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 Npositive 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:

解题思路:

模拟题,首先找到差最小的长和宽(遍历所有长宽,保存差最小的长和宽)

然后预先设置好四个移动方向(向上,向下,向左,向右) 顺序依次是右->下->左->上,按照这个规律移动

一旦超出界限或者该位子已经被占据,则改变移动方向,可以通过两个flag判断是上下移动还是左右移动,一般是先左右,再上下

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
int Martrix[101][101];
int mmove[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
int numbers[10010];
bool cmp(int a, int b) {
    return a > b;
}
int main() {
    int N;
    scanf("%d", &N);
    int minW, minL;
    int minDis = 0x7fffffff;
    //寻找差最小的长和宽
    for (int i = 1; i*i <= N; ++i) {
        if (N % i == 0) {
            if (((N / i) - i) < minDis) {
                minDis = (N / i) - i;
                minL = (N / i) > i ? (N / i) : i;
                minW = (N / i) < i ? (N / i) : i;
            }
        }
    }
    for (int i = 0; i < N; ++i) {
        scanf("%d", &numbers[i]);
    }
    sort(numbers, numbers + N, cmp);
    memset(Martrix, -1, sizeof(Martrix));
    int moveTriger = 0;
    bool leftRightTriger = true;
    bool updownTriger = false;
    int scounter = 0;
    int moveA = 0, moveB = 0;
    while (scounter < N) {
        if (leftRightTriger) {
            Martrix[moveA][moveB] = numbers[scounter];
            if (moveB + mmove[moveTriger][1] < 0 || moveB + mmove[moveTriger][1] >= minW || Martrix[moveA + mmove[moveTriger][0]][moveB + mmove[moveTriger][1]] != -1) {
                leftRightTriger = !leftRightTriger;
                updownTriger = !updownTriger;
                moveTriger++;
                if (moveTriger > 3) moveTriger = 0;
                moveA += mmove[moveTriger][0];
                moveB += mmove[moveTriger][1];
                scounter++;
                continue;
            }
            moveA += mmove[moveTriger][0];
            moveB += mmove[moveTriger][1];
        }
        if (updownTriger) {
            Martrix[moveA][moveB] = numbers[scounter];
            if (moveA + mmove[moveTriger][0] < 0 || moveA + mmove[moveTriger][0] >= minL || Martrix[moveA + mmove[moveTriger][0]][moveB + mmove[moveTriger][1]] != -1) {
                leftRightTriger = !leftRightTriger;
                updownTriger = !updownTriger;
                moveTriger++;
                if (moveTriger > 3) moveTriger = 0;
                moveA += mmove[moveTriger][0];
                moveB += mmove[moveTriger][1];
                scounter++;
                continue;
            }
            moveA += mmove[moveTriger][0];
            moveB += mmove[moveTriger][1];
        }
        scounter++;
    }
    for (int i = 0; i < minL; ++i) {
        for (int j = 0; j < minW; ++j) {
            printf("%d", Martrix[i][j]);
            if (j < minW - 1) printf(" ");
        }
        cout << endl;
    }
    system("PAUSE");
    return 0;
}