leetcode回顾——Spiral Matrix III

LeetCode

题目

On a 2 dimensional grid with R rows and C columns, we start at (r0, c0) facing east.

Here, the north-west corner of the grid is at the first row and column, and the south-east corner of the grid is at the last row and column.

Now, we walk in a clockwise spiral shape to visit every position in this grid.

Whenever we would move outside the boundary of the grid, we continue our walk outside the grid (but may return to the grid boundary later.)

Eventually, we reach all R * C spaces of the grid.

Return a list of coordinates representing the positions of the grid in the order they were visited.

Example 1:

Input: R = 1, C = 4, r0 = 0, c0 = 0
Output: [[0,0],[0,1],[0,2],[0,3]]

Example 2:

Input: R = 5, C = 6, r0 = 1, c0 = 4
Output: [[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]]

解析

这道题其实很简单，按照它说的规则来就好了；点从（r0, c0）位置出发，以方向为右——>——>下——>左——>上的绕圈走法，而我们需要去记录这种走法所经过的二维表的格子位置，仔细观察这种走法，可以发现这种规律

向右走与向左走

点首先从（r0, c0）出发向右走一格，当他要向左走时，向左走的格数是上一次向右走的格子数加上一，同理，向右走的格子数是上一次向左走的格子数加一

向上走与向下走

向上走与向下走的规律和上面的规律一样

规律分析清楚了，那么，怎么实现呢？可以设置一个长度为5的int类型的数组direction，数组内部存储的数据如下

1
direction = [0, 1, 2, -1, -2]  (1 代1表向右走，2 代表向下走，-1 代表向左走，-2 代表向上走)

同时，设置一个方向标记index，记录行走的方向，当index为4时，代表此时点已经以向上的方向走完了相应的格子数，这时，又重新回到了右——>——>下——>左——>上的绕圈走法，因此将index置为0，待index自增后重新开始指向向右走的方向

解题代码

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution:
    def spiralMatrixIII(self, R, C, r0, c0):
        """
        :type R: int
        :type C: int
        :type r0: int
        :type c0: int
        :rtype: List[List[int]]
        """
        lateral = 1
        vertical = 1
        road = [[r0, c0]]
        r0_t = r0
        c0_t = c0
        if 0 <= R <= 100 and 0 <= C <= 100:
            if 0 <= r0 < R and 0 <= c0 < C:

                max_grid_num = R * C

                direction = [0, 1, 2, -1, -2]
                index = 1
                total_road_len = 0
                while len(road) < max_grid_num:
                    road_tmp = None
                    _dir = direction[index]
                    if _dir == 1 or _dir == -1:
                        road_tmp, r0_t, c0_t = self.draw_guiji(
                            r=r0_t, c=c0_t, lateral=lateral, vertical=None, dir_type=int(_dir / 1), R=R, C=C)
                        lateral += 1
                    elif _dir == 2 or _dir == -2:
                        road_tmp, r0_t, c0_t = self.draw_guiji(
                            r=r0_t, c=c0_t, lateral=None, vertical=vertical, dir_type=int(_dir / 2), R=R, C=C)
                        vertical += 1
                        if _dir == -2:
                            index = 0
                    index += 1
                    road.extend(road_tmp)
        return road

    def draw_guiji(self, r, c, lateral, vertical, dir_type, R, C):
        road = []
        if vertical is None:
            for item in range(1, lateral + 1):
                c += dir_type * 1
                if r >= R or r < 0 or c >= C or c < 0:
                    continue
                road.append([r, c])
        if lateral is None:
            for item in range(1, vertical + 1):
                r += dir_type * 1
                if r >= R or r < 0 or c >= C or c < 0:
                    continue
                road.append([r, c])
        return road, r, c


if __name__ == '__main__':
    s = Solution()
    print(s.spiralMatrixIII(R=1, C=4, r0=0, c0=0))