上海计算机学会2026年4月月赛C++丙组T3 螺旋矩阵

螺旋矩阵

题目描述

给定一个正整数NNN，请打印出一个N×NN \times NN×N的螺旋矩阵。

螺旋矩阵定义如下：从左上角出发，初始时向右移动，如果前方是没有经过的格子，则继续前进，否则，右转九十度。重复上述操作直到经过所有格子，按照先后顺序填充数字111到N2N^2N2。

下图是N=4N=4N=4时的螺旋矩阵：

1 2 3 4 12 13 14 5 11 16 15 6 10 9 8 7

输入格式

单个整数：表示NNN

输出格式

输出一个N×NN \times NN×N的螺旋矩阵

数据范围

1≤N≤3001 \leq N \leq 3001≤N≤300

样例数据

输入

4

输出

1 2 3 4 12 13 14 5 11 16 15 6 10 9 8 7

题解

我采用方向数组模拟的方法解决螺旋矩阵问题，核心思路是按照右、下、左、上的顺序循环移动，遇到边界或已填充的数字时转向，直到填满整个矩阵。

完整代码（仅添加注释，不修改逻辑）

#include<bits/stdc++.h>usingnamespacestd;// 定义最大数组，满足N≤300的要求inta[305][305];// 存储输入的矩阵边长intn;// 方向数组：右、下、左、上 四个方向的x坐标偏移量intdx[]={0,1,0,-1};// 方向数组：右、下、左、上 四个方向的y坐标偏移量intdy[]={1,0,-1,0};intmain(){// 输入矩阵边长ncin>>n;// 初始位置：左上角(1,1)intx=1,y=1;// 初始方向：0代表向右intf=0;// 循环填充1~n²的所有数字for(inti=1;i<=n*n;i++){// 将当前数字填入对应位置a[x][y]=i;// 计算下一步要移动到的坐标intxx=x+dx[f];intyy=y+dy[f];// 判断下一步坐标是否合法（在矩阵内+未被填充）if(xx>=1&&xx<=n&&yy>=1&&yy<=n&&a[xx][yy]==0){// 合法则直接移动x=xx;y=yy;}else{// 不合法则右转（方向+1，对4取模实现循环）f++;f%=4;// 按照新方向移动一步x+=dx[f];y+=dy[f];}}// 遍历输出整个矩阵for(inti=1;i<=n;i++){for(intj=1;j<=n;j++){cout<<a[i][j]<<" ";}// 每行输出完毕后换行cout<<"\n";}return0;}

代码说明

1. 方向数组设计：dx和dy分别对应右、下、左、上四个方向的坐标偏移，通过切换数组下标实现转向。
2. 移动逻辑：从起点开始，每次尝试向当前方向前进，若位置合法则移动，不合法则右转后再移动。
3. 边界判断：严格限制坐标在1∼n1 \sim n1∼n范围内，同时判断目标位置是否未被填充（值为0）。
4. 输出：双层循环遍历二维数组，按行打印螺旋矩阵。

该算法时间复杂度为O(N2)O(N^2)O(N2)，空间复杂度为O(N2)O(N^2)O(N2)，完美适配题目N≤300N \leq 300N≤300的数据范围。

总结

1. 我用方向数组模拟螺旋移动的路径，实现了螺旋矩阵的填充；
2. 核心逻辑是合法则前进，不合法则转向；
3. 代码时间复杂度最优，能高效处理题目给定的数据范围。