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

秒速五厘米 2022-04-23 06:58 157阅读 0赞

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

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

解题思路:

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

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

一旦超出界限或者该位子已经被占据,则改变移动方向,可以通过两个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;
    }