P2529. 螺旋数字矩阵

解题思路

注意，本题和 经典题型、螺旋矩阵 非常类似。

本题既可以用 迭代方法 也可以用 递归方法 完成。本题解主要介绍 递归方法。

确定矩阵列数

题目要求矩阵列数尽可能少，使用 向上取整，很容易算出来最小的列数为 c = ceil(n / m)。

填充过程示例

注意到每次填充都优先填充矩阵的 最外圈。比如对于 5×5 的矩阵，初始化均用 * 填充：

假设需要填充 21 个数，那么第一圈会螺旋式地填充如下：

中间剩余一个 (5-2)*(5-2) = 3*3 的未填充矩阵，那么可以从 17 开始继续螺旋式地填充第二层矩阵，直到到达 21，即：

显然每一次填充，都是从未填充矩阵的 左上角 开始填充其 外层，直到填充完毕或到达规定数字。因此可以使用 递归 来完成上述过程。

初始化矩阵

首先我们需要初始化一个均由 "*" 填充的 m*c 的二维矩阵 ans。

递归函数参数

在递归过程中，我们需要四个参数 start_i, end_i, start_j, end_j，分别为子矩阵的起始、终止的 i 和 j 下标。即：

• cur_num 为未填充子矩阵左上角的第一个数
• n 为填充结束的终止数字

填充上边界

以填充子矩阵的 上边界 为例，我们需要固定 start_i，从左往右（从 start_j 到 end_j）遍历 j。在遍历过程中，我们需要把 ans[start_i][j] 修改为 str(cur_num)，同时增加 cur_num，且一旦发现 cur_num > n，则可以直接退出函数。

填充四个方向

同理我们可以构建出填充子矩阵其他遍历方向的代码：

递归调用

在所有遍历和边界填充完成之后，我们需要进行递归函数的调用。注意到在下一层递归中，四个边界分别变成了 start_i+1, end_i-1, start_j+1, end_j-1。

特殊情况处理

除此之外，还需要考虑一种 特殊情况。如果遍历区间不存在，则不会进入四个 for 循环中的任意一个，会持续进行递归，导致 编译栈溢出。这种情况就是当 n 为某个奇数的平方且 c = m = sqrt(n) 的时候会出现。譬如填充 5×5 的矩阵且 n = 25，最中间那个数字会出现的情况。我们还需要额外判断这种条件，将最中间的数字填充上并退出递归即可。

递归入口

剩下的内容就是递归入口的调用了。分别对 start_i, end_i, start_j, end_j 传入 0, m-1, 0, c-1 即可。cur_num 则传入第一个需要填充的数字 1。

复杂度分析 设 m 为行数，c = ceil(n / m) 为列数。递归的每一层负责填充当前未填充子矩阵的最外圈：四个 for 循环各沿一条边走一遍，每个格子至多被填写一次，一旦 cur_num 超过终止数字 n 就立即 return，不再做任何多余工作。因此填充的总工作量与矩阵规模成正比，时间复杂度为 O(m*c)，其中 c 由 n 与 m 决定。空间上，答案矩阵本身占 O(m*c)；递归每深入一层，四个边界各向内收缩一格，递归深度约为 min(m, c)/2，递归栈的额外开销为 O(min(m, c))，整体空间复杂度为 O(m*c)。