題目敘述:
給定一個二維陣列的高與寬，並且給定起點位置座標。
請從起點位置開始順時針拜訪陣列元素，並且把沿路走過的座標記錄下來。
以陣列的形式返回答案。測試範例
Example 1:
Input: rows = 1, cols = 4, rStart = 0, cStart = 0
Output: [[0,0],[0,1],[0,2],[0,3]]
Example 2:
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]]
約束條件
Constraints:
1 <= rows, cols <= 100
陣列的高和寬都介於1~100之間。
0 <= rStart < rows
起點的row一定是合法位置。
0 <= cStart < cols
起點的column一定是合法位置。
演算法 模擬順時針走法
順時針拜訪方向固定是往右，往下，往左，往上。
初始step步伐為一步。
進入迴圈
接著往右step步，往下step步。
step 累加多一步
接著往左step步，往上step步。
step 累加多一步
...如此反覆循環，一直到拜訪所有陣列的格子點為止。
程式碼 模擬順時針走法
class Solution():
def spiralMatrixIII(self, R, C, r0, c0):
# path, initialized on starting point
path = [(r0, c0)]
is_valid = lambda row, col: 0 <= row < R and 0 <= col < C
# length of steps to move
steps = 1
r, c = r0, c0
# Keep walking until all grids are visited
while len(path) < R * C:
# Go east
for step in range(steps):
r, c = r, c + 1
if is_valid(r, c): path.append((r, c))
# Go down
for step in range(steps):
r, c = r + 1, c
if is_valid(r, c): path.append((r, c))
steps += 1
# Go west
for step in range(steps):
r, c = r, c - 1
if is_valid(r, c): path.append((r, c))
# Go north
for step in range(steps):
r, c = r - 1, c
if is_valid(r, c): path.append((r, c))
steps += 1
return path
複雜度分析
時間複雜度: O( Max{R, C}^2)
相當於以起點為圓心，邊長為半徑，以同心圓擴散，
順時針走的圖形，走的軌跡是一個回字型。
所需時間 = O( Max{R, C}^2) ~ (比較長的邊長)的平方
空間複雜度: O( R * C )
需要額外一個陣列去儲存走過的格子點，格子點總數 = 陣列大小 = R * C
