跳转至

LeetCode: 885. 螺旋矩阵 III

1、题目描述

RC 列的矩阵上,我们从 (r0, c0) 面朝东面开始

这里,网格的西北角位于第一行第一列,网格的东南角位于最后一行最后一列。

现在,我们以顺时针按螺旋状行走,访问此网格中的每个位置。

每当我们移动到网格的边界之外时,我们会继续在网格之外行走(但稍后可能会返回到网格边界)。

最终,我们到过网格的所有 R * C 个空间。

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

示例 1:

输入:R = 1, C = 4, r0 = 0, c0 = 0
输出:[[0,0],[0,1],[0,2],[0,3]]

img

示例 2:

输入:R = 5, C = 6, r0 = 1, c0 = 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]]

img

提示:

  • 1 <= R <= 100
  • 1 <= C <= 100
  • 0 <= r0 < R
  • 0 <= c0 < C

2、解题思路

  • 使用0,1,2,3分别表示东南西北
  • 转向带有步伐,初始步伐是1,走一步则转向
  • 转向两次步伐增加一步,循环控制,一直到所有的坐标都被放入结果集中
class Solution:
    def spiralMatrixIII(self, R: int, C: int, r0: int, c0: int) -> List[List[int]]:
        res = []
        direction = 0
        direction_count = 0
        step = 1
        step_count = 0

        def available(x, y):
            return 0 <= x < R and 0 <= y < C

        m, n = r0, c0
        while len(res) < (R * C):
            if available(m, n):
                res.append([m, n])

            if direction == 0:
                m, n = m, n + 1

            elif direction == 1:
                m, n = m + 1, n
            elif direction == 2:
                m, n = m, n - 1
            elif direction == 3:
                m, n = m - 1, n

            step_count += 1
            # 转向判断
            if step_count == step:
                step_count = 0
                direction = (direction + 1) % 4
                direction_count += 1
                if direction_count == 2:
                    step += 1
                    direction_count = 0
        return res