## Spiral Matrix III

• Time:O(\max^2(R, C))
• Space:O(R \cdot C)

## C++

class Solution {
public:
vector<vector<int>> spiralMatrixIII(int R, int C, int r0, int c0) {
vector<vector<int>> ans{{r0, c0}};
vector<int> dx{1, 0, -1, 0};
vector<int> dy{0, 1, 0, -1};

for (int i = 0; ans.size() < R * C; ++i)
for (int step = 0; step < i / 2 + 1; ++step) {
r0 += dy[i % 4];
c0 += dx[i % 4];
if (0 <= r0 && r0 < R && 0 <= c0 && c0 < C)
ans.push_back({r0, c0});
}

return ans;
}
};


## JAVA

class Solution {
public int[][] spiralMatrixIII(int R, int C, int r0, int c0) {
List<int[]> ans = new ArrayList<>();
final int[] dx = {1, 0, -1, 0};
final int[] dy = {0, 1, 0, -1};

ans.add(new int[] {r0, c0});

for (int i = 0; ans.size() < R * C; ++i)
for (int step = 0; step < i / 2 + 1; ++step) {
r0 += dy[i % 4];
c0 += dx[i % 4];
if (0 <= r0 && r0 < R && 0 <= c0 && c0 < C)
ans.add(new int[] {r0, c0});
}

return ans.toArray(new int[ans.size()][]);
}
}


## Python

class Solution:
def spiralMatrixIII(self, R: int, C: int, r0: int, c0: int) -> List[List[int]]:
ans = [[r0, c0]]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
i = 0

while len(ans) < R * C:
for _ in range(i // 2 + 1):
r0 += dy[i % 4]
c0 += dx[i % 4]
if 0 <= r0 < R and 0 <= c0 < C:
ans.append([r0, c0])
i += 1

return ans