PAT A1105 Spiral Matrix(C++)

发表于 | 分类于 | |
字数统计: 546 字 | 阅读时长 ≈ 3 分钟
PAT甲级目录 | PAT乙级目录

题目描述

原题地址：A1105 Spiral Matrix
中文版：B1050 螺旋矩阵

解题思路

设置一个二维数组，将结果按照螺旋填充到二维数组中再最后输出。填充注意不要超出边界。用二维数组的默认值来表示该位置未被填充，以实现隐形的不断缩小的边界。

易错点

  • ans[i][++j]
    • 使用 ++j 可以使得下一步循环的 j 为同一个 j；
    • 否则要另外考虑只剩最中间一行或一列的情况；多多试错，总能 AC

也许陌生的知识点

  • sort(S, S + N, cmp);
    • 排序函数，实现 [first, last) 范围内的排序，可以自定义排序策略 cmp 函数
    • 所需头文件： algorithm
  • memset(s,0,sizeof(s));
    • 将 s 所指向的某一块内存中的后一定范围内的内容全部设置为指定的 ASCII 值， memset(<内存地址>, <指定的 ASCII 码>, <地址大小>);
    • memset 函数按字节对内存块进行初始化，所以不能用它将 int 数组初始化为 0 和 -1 之外的其他值
    • 所需头文件：cstring
  • char a[5]; memset(a, 97, 5 * sizeof(char));
    • 可将字符数组 a 初始化为 aaaaa；

代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
bool cmp(int a, int b){ return a > b; }
int main(){
  int N, S[10010];
  scanf("%d", &N);
  int n = (int)sqrt(1.0 * N);
  while(N % n != 0) n--;
  int m = N / n;
  int ans[m][n];
  memset(ans,0,sizeof(ans));//用于判断是否被赋值过
  for(int i = 0; i < N; i++) scanf("%d", &S[i]);
  sort(S, S + N, cmp);
  int i = 0, j = 0, k = 0;
  ans[i][j] = S[k++];//第一个赋值
  while(k < N){
    while(j < n - 1 && !ans[i][j+1]) ans[i][++j] = S[k++];//从左向右
    while(i < m - 1 && !ans[i+1][j]) ans[++i][j] = S[k++];//从上向下
    while(j > 0 && !ans[i][j-1]) ans[i][--j] = S[k++];//从右往左
    while(i > 0 && !ans[i-1][j]) ans[--i][j] = S[k++];//从下往上
  }
  for(int i = 0; i < m; i++){
    for(int j = 0; j < n; j++){
      if(j != 0) printf(" ");
      printf("%d", ans[i][j]);
    }
    printf("\n");
  }
  return 0;
}