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 north-west corner of the grid is at the first row and column, and the south-east 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]]

Image text

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]]

Image text

Note:

  1. 1 <= R <= 100
  2. 1 <= C <= 100
  3. 0 <= r0 < R
  4. 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;
    }
}

All Problems

All Solutions