https://leetcode.com/problems/spiral-matrix-iii
※ 引述《involution ( )》之铭言：
: 885. Spiral Matrix III
: 无聊的模拟题 只是想分享一下绕圈圈的四个方向有几种写法
: 1.
: direction = [[0, 1], [1, 0], [0, -1], [-1, 0]]
: 非常标准的写法，分别写出四个方向的xy移动量
: 2.
: dx = [0, 1, 0, -1]
: dy = [1, 0, -1, 0]
: 跟上面就是 AoS/SoA 的差别，也很常见
: 3.
: direction = [0, 1, 0, -1, 0]
: 观察之后会发现 [direction[i:i+2] for i in range(4)]
: 刚好就和第一种写法是一样的结果
: 是一个有趣但如果有其他人要看你code就不适合的写法
: 4.
: dx, dy = dy, -dx
: 我觉得也是巧合，不过硬要解释说这就是顺时针旋转也解释的通（外积之类的）
: 反正如果需要跟人解释的话我不会这么写
: :)
给一个起始点 (rStart, cStart) 跟网格 rows x cols
面向东顺时针走 超出网格范围也会继续行走 直到网格的所有空间都走过一遍
根据碰到的网格顺序 回传座标数组
Example 1:
https://s3-lc-upload.s3.amazonaws.com/uploads/2018/08/24/example_1.png
Input: rows = 1, cols = 4, rStart = 0, cStart = 0
Output: [[0,0],[0,1],[0,2],[0,3]]
Example 2:
https://s3-lc-upload.s3.amazonaws.com/uploads/2018/08/24/example_2.png
Input: rows = 5, cols = 6, rStart = 1, cStart = 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]]
思路：走法分4种 steps = [[0, 1], [1, 0], [0, -1], [-1, 0]]
可以发现每种走法的次数是 1, 1, 2, 2, 3, 3, 4, 4, ...
所以每2个走法 走的次数要 +1
最后循环直到答案数量满足 rows * cols
Python Code:
class Solution:
def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int)
-> List[List[int]]:
step = 1
st = 0
steps = [[0, 1], [1, 0], [0, -1], [-1, 0]]
answer = [[rStart, cStart]]
total = rows * cols - 1
while total:
for i in range(step):
rStart += steps[st % 4][0]
cStart += steps[st % 4][1]
if 0 <= rStart < rows and 0 <= cStart < cols:
answer.append([rStart, cStart])
total -= 1
if not total:
return answer
if st % 2:
step += 1
st += 1
return answer
https://i.imgur.com/J69Filp.png