Sponsored
Sponsored
To simulate walking in a spiral, maintain a direction vector and a step count for each segment. Initially face east, and keep track of direction changes in the order of east, south, west, north. After two direction changes, increase the step count which determines how far to walk in the current direction before turning.
Time Complexity: O(rows * cols), since each cell is visited once,
Space Complexity: O(rows * cols), for the result storage.
1def spiralMatrixIII(R, C, r0, c0):
2 res = [(r0, c0)]
3 steps = 1
4 # Directions: right, down, left, up
5 directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
6 while len(res) < R * C:
7 for i in range(4):
8 if i == 0 or i == 2:
9 for _ in range(steps):
10 r0 += directions[i][0]
11 c0 += directions[i][1]
12 if 0 <= r0 < R and 0 <= c0 < C:
13 res.append((r0, c0))
14 else:
15 for _ in range(steps):
16 r0 += directions[i][0]
17 c0 += directions[i][1]
18 if 0 <= r0 < R and 0 <= c0 < C:
19 res.append((r0, c0))
20 steps += 1
21 return resThis Python solution uses direction vectors to simulate movement in a grid. Each directional change is associated with appropriate step increments.