螺旋矩阵 III

难度: Medium

在 rows x cols 的网格上，你从单元格 (rStart, cStart) 面朝东面开始。网格的西北角位于第一行第一列，网格的东南角位于最后一行最后一列。

你需要以顺时针按螺旋状行走，访问此网格中的每个位置。每当移动到网格的边界之外时，需要继续在网格之外行走（但稍后可能会返回到网格边界）。

最终，我们到过网格的所有 rows x cols 个空间。

按照访问顺序返回表示网格位置的坐标列表。

示例 1：

输入：rows = 1, cols = 4, rStart = 0, cStart = 0
输出：[[0,0],[0,1],[0,2],[0,3]]

示例 2：

输入：rows = 5, cols = 6, rStart = 1, cStart = 4
输出：[[1,4],[1,5],[2,5],[2,4],[2,3],[1,3],[0,3],[0,4],[0,5],[3,5],[3,4],[3,3],[3,2],[2,2],[1,2],[0,2],[4,5],[4,4],[4,3],[4,2],[4,1],[3,1],[2,1],[1,1],[0,1],[4,0],[3,0],[2,0],[1,0],[0,0]]

提示：

1 <= rows, cols <= 100
0 <= rStart < rows
0 <= cStart < cols

Submission

运行时间: 39 ms

内存: 17.2 MB

# class Solution:
#     def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:


class Solution:
    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:
        res = []
        x, y, dx, dy, n = rStart, cStart, 0, 1, 0
        while len(res) < rows * cols:
            for _ in range(n // 2 + 1):
                if 0 <= x < rows and 0 <= y < cols:
                    res.append([x, y])
                x, y = x + dx, y + dy
            dx, dy, n = dy, -dx, n + 1
        return res

Explain

该题解采用模拟螺旋行走的方式遍历整个网格。从指定的起始点 (rStart, cStart) 开始，沿着东南西北的顺序不断地转向。题解中使用 (dx, dy) 来表示当前行走的方向，初始化为向东 (0, 1)。每走完一个方向的两次行走后，行走的距离会增加。具体实现时，根据变量 n 来动态调整每次行走的步数。行走时检查当前坐标是否在网格内，如果在则加入结果列表。行走的方向通过交换 dx 和 dy 并改变 dy 的符号来实现顺时针旋转。

时间复杂度: O(rows * cols)

空间复杂度: O(rows * cols)

# class Solution:
#     def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:


class Solution:
    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:
        res = []  # 结果列表
        x, y, dx, dy, n = rStart, cStart, 0, 1, 0  # 初始化位置和方向
        while len(res) < rows * cols:  # 直到所有格子都被访问
            for _ in range(n // 2 + 1):  # 根据 n 计算此方向上的步数
                if 0 <= x < rows and 0 <= y < cols:  # 检查是否在网格内
                    res.append([x, y])  # 在网格内则记录位置
                x, y = x + dx, y + dy  # 向当前方向移动
            dx, dy, n = dy, -dx, n + 1  # 改变方向并增加步数
        return res  # 返回结果

Explore

在螺旋矩阵III的实现中，该循环结构通过逐步增加步数来模拟螺旋运动。具体来说，每次改变方向后，`n`会增加1，因此每两次方向改变后，行走步数会逐渐增加。通过`n // 2 + 1`的计算，可以在每次方向改变时逐步增加该方向的步数，从而保证每个方向上的覆盖范围逐渐扩大，以适应螺旋结构。在实现中，每次循环会尝试向前走这么多步，并检查每一步是否在网格内，从而确保了所有网格位置都有机会被访问到。

算法中的方向变换`dx, dy = dy, -dx`基于二维坐标旋转的数学原理。在标准的二维坐标系中，顺时针旋转一个向量可以通过一个旋转矩阵来实现。对于90度顺时针旋转，旋转矩阵是`[[0, 1], [-1, 0]]`。应用这个矩阵到向量(dx, dy)，结果向量为(dy, -dx)。因此，当你按这个规则更新(dx, dy)时，它实际上是将当前的行走方向旋转了90度顺时针，从而使得行走路径符合螺旋的顺时针方向。

`n`变量在螺旋遍历过程中起到了控制行走步数和方向变换的关键作用。初始时`n`为0，每完成一个方向的行走，`n`就增加1。由于每两次方向变换后行走的步数需要增加1，`n`被用来计算当前方向上行走的步数，通过`n // 2 + 1`的计算公式。这种递增的步数模式使得螺旋的半径随着行进的过程逐渐增大，确保了遍历可以覆盖更大区域的网格。同时，每次方向更改时，都会使用`dx, dy = dy, -dx`来更新行走方向，保持顺时针螺旋的一致性。