Formatted question description: https://leetcode.ca/all/885.html
885. Spiral Matrix III
Level
Medium
Description
On a 2 dimensional grid with R
rows and C
columns, we start at (r0, c0)
facing east.
Here, the northwest corner of the grid is at the first row and column, and the southeast corner of the grid is at the last row and column.
Now, we walk in a clockwise spiral shape to visit every position in this grid.
Whenever we would move outside the boundary of the grid, we continue our walk outside the grid (but may return to the grid boundary later.)
Eventually, we reach all R * C
spaces of the grid.
Return a list of coordinates representing the positions of the grid in the order they were visited.
Example 1:
Input: R = 1, C = 4, r0 = 0, c0 = 0
Output: [[0,0],[0,1],[0,2],[0,3]]
Example 2:
Input: R = 5, C = 6, r0 = 1, c0 = 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]]
Note:
1 <= R <= 100
1 <= C <= 100
0 <= r0 < R
0 <= c0 < C
Solution
Starting from (r0, c0)
, visit the cells and store the visited cells’ rows and columns. How many cells are visited each time in one direction? After visiting (r0, c0)
, move east by 1 step, and then move south by 1 step. After the two directions, move west by 2 steps, and then move north by 2 steps. It can be seen that the number of steps in each direction increases by 1 for every two directions. In this way, there won’t be any cell that is visited more than once. Continue visiting the cells in this way.
It is possible that a coordinate is out of the boundary of the grid. To store the visited cell’s rows and columns, only store the cells that are inside the boundary of the grid. The visiting procedure ends when all cells inside the boundary of the grid are visited.
Java

class Solution { public int[][] spiralMatrixIII(int R, int C, int r0, int c0) { int cells = R * C; int[][] order = new int[cells][2]; order[0][0] = r0; order[0][1] = c0; int count = 1, fillCount = 1; int[] currentCell = new int[2]; currentCell[0] = r0; currentCell[1] = c0; int[][] directions = { {0, 1}, {1, 0}, {0, 1}, {1, 0} }; while (fillCount < cells) { int step = (count + 1) / 2; int[] direction = directions[(count  1) % 4]; for (int i = 0; i < step; i++) { for (int j = 0; j < 2; j++) currentCell[j] += direction[j]; if (currentCell[0] >= 0 && currentCell[0] < R && currentCell[1] >= 0 && currentCell[1] < C) { for (int j = 0; j < 2; j++) order[fillCount][j] = currentCell[j]; fillCount++; } } count++; } return order; } }

// OJ: https://leetcode.com/problems/spiralmatrixiii/ // Time: O(max(R, C)^2) // Space: O(1) class Solution { private: vector<vector<int>> ans; int r, c; void add(int x, int y) { if (x < 0  x >= r  y < 0  y >= c) return; ans.push_back({ x, y }); } public: vector<vector<int>> spiralMatrixIII(int R, int C, int r0, int c0) { r = R; c = C; int x = r0, y = c0, cnt = R * C, d = 2; ans.push_back({ x, y }); while (ans.size() < cnt) { add(x, ++y); for (int i = 1; i < d; ++i) add(++x, y); for (int i = 0; i < d; ++i) add(x, y); for (int i = 0; i < d; ++i) add(x, y); for (int i = 0; i < d; ++i) add(x, ++y); d += 2; } return ans; } };

class Solution(object): def spiralMatrixIII(self, R, C, r0, c0): """ :type R: int :type C: int :type r0: int :type c0: int :rtype: List[List[int]] """ def nxt(r, c): step = 1 yield (r, c) while True: for _ in range(step): c += 1 yield (r, c) for _ in range(step): r += 1 yield (r, c) step += 1 for _ in range(step): c = 1 yield (r, c) for _ in range(step): r = 1 yield (r, c) step += 1 ans = [] for r, c in nxt(r0, c0): if 0 <= r < R and 0 <= c < C: ans.append([r, c]) if len(ans) == R * C: break return ans