Solution
The idea is to move through the whole path and whenever we come inside the grid, we add the element to the answer. Now, how do we move along the path? If you observe carefully, there is patter in the steps:
move right 1 step, turn right
move down 1 step, turn right
move left 2 steps, turn right
move top 2 steps, turn right
move right 3 steps, turn right
move down 3 steps, turn right
move left 4 steps, turn right
move top 4 steps, turn right
Notice the pattern: 1,1,2,2,3,3,4,4,5,5...
Let n be index of this sequence.
Then A0 = 1, A1 = 1, A2 = 2 and so on
We can find that An = n/2 + 1
Now we just have to figure out how to turn right. There is a general method to rotate when traversing a matrix. We define two arrays:
vector<int> dx = {0, 1, 0, -1}; // right, down, left, up
vector<int> dy = {1, 0, -1, 0}; // right, down, left, up
Suppose we are on coordinate {x, y}. {x+dx[0], y+dy[0]} is then the coordinate after taking a step towards right. {x+dx[1], y+dy[1]} is then the coordinate after taking a step towards down. And so on…
Code:
vector<vector<int>> spiralMatrixIII(int R, int C, int r0, int c0) {
vector<int> dx = {0, 1, 0, -1};
vector<int> dy = {1, 0, -1, 0};
vector<vector<int>> res;
int x = r0, y=c0, n=0, k=0;
while (res.size() != R*C) {
// n/2+1 steps in the same direction
for (int i=0; i<n/2+1; i++) {
if (x>=0 && x<R && y>=0 && y<C) {
res.push_back({x, y});
}
x += dx[k%4];
y += dy[k%4];
}
// rotate next time
k++;
n++;
}
return res;
}