个人练习-PAT甲级-1105 Spiral Matrix

本文主要是介绍个人练习-PAT甲级-1105 Spiral Matrix，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接https://pintia.cn/problem-sets/994805342720868352/problems/994805363117768704

题目大意，给出一串序列，要求将其按顺时针顺序填入一个m*n的矩阵中，其中m>n且m-n最小。

简单题，只需要注意顺时针这个顺序即可。先求m和n。

    m = (int)(sqrt(1.0*N));while (N % m != 0) {m++;}n = N / m;if (m < n) {int tmp = m;m = n;n = tmp;}

p和q表示下一个填入矩阵的位置，限定p和q的上下限，用dir表示指针移动的方向。

    int p = 0, q = 0, pos = N-1, dir = 1;int pmin = 1, pmax = m-1, qmin = 0, qmax = n-1;while (pos != -1) {mat[p][q] = arr[pos--];if (dir == 1) {if (q < qmax) q++;else {qmax--; p++; dir = 2;}}else if (dir == 2) {if (p < pmax) p++;else {pmax--; q--; dir = 3;}}else if (dir == 3) {if (q > qmin) q--;else {qmin++; p--; dir = 4;}}else {if (p > pmin) p--;else {pmin++; q++; dir = 1;}}}

完整代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>using namespace std;vector<int> arr;
int mat[102][102];
int N, m, n;int main() {scanf("%d", &N);arr.resize(N);for (int i = 0; i < N; i++) {scanf("%d", &arr[i]);}sort(arr.begin(), arr.end());m = (int)(sqrt(1.0*N));while (N % m != 0) {m++;}n = N / m;if (m < n) {int tmp = m;m = n;n = tmp;}int p = 0, q = 0, pos = N-1, dir = 1;int pmin = 1, pmax = m-1, qmin = 0, qmax = n-1;while (pos != -1) {mat[p][q] = arr[pos--];if (dir == 1) {if (q < qmax) q++;else {qmax--; p++; dir = 2;}}else if (dir == 2) {if (p < pmax) p++;else {pmax--; q--; dir = 3;}}else if (dir == 3) {if (q > qmin) q--;else {qmin++; p--; dir = 4;}}else {if (p > pmin) p--;else {pmin++; q++; dir = 1;}}}for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (j != 0)printf(" ");printf("%d", mat[i][j]);if (j == n-1)printf("\n");}}return 0;
}