PAT-A 真题 – 1105 Spiral Matrix

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 \times n$ must be equal to $N$ ; $m \geq 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 $1 0^{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:

题目大意见：https://www.mmuaa.com/post/d0bd286fb11fac92.html

时隔一年后，再次写到这道题，没有刷乙级时候那么费脑细胞了hhh

#include <cstdio>
#include <iostream>
#include <algorithm> 
#include <cmath>
using namespace std;

int GetWidth(int n){
  int ans = sqrt(n);
  while(n%ans) ans--;
  return ans;
}

int main(){
  int n;
  cin >> n;
  int W = GetWidth(n), H = n / W;
  int mat[W][H], num[n];
  fill(mat[0], mat[0] + W * H, -1);
  for(int i = 0; i < n; i++)
    cin >> num[i];
  sort(num, num + n);
  int direct = 0;  //方向。0右，1下，2左，3上 
  int offset[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};  //偏移量 
  int x = 0, y = 0;  //初始位置在(0, 0) 
  for(int i = n-1; i >= 0; i--){
    //将数字插入到螺旋矩阵中
    mat[x][y] = num[i];
    //printf("当前数据：%d，方向：%d，坐标(%d,%d)\n",num[i], direct, x, y);
    //越界判断
    switch(direct){
      case 0:  //当前正在往右走 
        if(x != W-1 && mat[x+1][y] == -1)  //尚未越界
          break;
        else  //右方越界
          direct = 1;  //往下走
        break;
      case 1:  //当前正在往下走
        if(y != H-1 && mat[x][y+1] == -1)  //尚未越界
          break;
        else   //下方越界 
          direct = 2;  //往左走
        break;
      case 2:  //当前正在往左走
        if(x != 0 && mat[x-1][y] == -1)  //尚未越界
          break;
        else  //左方越界
          direct = 3;  //往上走
      case 3:  //当前正在往上走
        if(y != 0 && mat[x][y-1] == -1)  //尚未越界
          break;
        else  //上方越界
          direct = 0;  //往右走 
    }
    x += offset[direct][0];
    y += offset[direct][1];
  }
  for(int y = 0; y < H; y++){
    for(int x = 0; x < W; x++){
      cout << mat[x][y];
      if(x != W-1) cout << ' ';
    }
    cout << endl;
  }
  return 0;
}

斐斐のBlog