PAT A1105 Spiral Matrix(C++)

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;
}