885. Spiral Matrix III #

Problem #

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

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

Problem Summary #

On a matrix with R rows and C columns, we start at (r0, c0) facing east. Here, the northwest corner of the grid is located at the first row and first column, and the southeast corner of the grid is located at the last row and last column. Now, we walk clockwise in a spiral shape, visiting every position in this grid. Whenever we move outside the boundary of the grid, we continue walking outside the grid (but may return to the grid boundary later). Eventually, we have visited all R * C spaces of the grid.

The requirement is to output a list of coordinates representing the grid positions in the order they were visited.

Solution Approach #

• Given the rows R and columns C of a two-dimensional array, as well as the starting point (r0,c0) in this array. Starting from this point, visit each point in the array in a spiral order, and output every coordinate passed along the way. Note that the step length of each spiral increases: the first spiral has 1 step, the second spiral has 1 step, the third spiral has 2 steps, the fourth spiral has 2 steps… that is, the step lengths are 1, 1, 2, 2, 3, 3, 4, 4, 5…
• This problem is an enhanced version of Problem 59. In addition to the spiral, it also adds a constraint on step length. The step length actually follows a pattern: the step length of the 0th move is 0/2+1, the step length of the 1st move is 1/2+1, and the step length of the nth move is n/2+1. The rest of the approach is the same as Problem 59.

Code #

package leetcode

func spiralMatrixIII(R int, C int, r0 int, c0 int) [][]int {
	res, round, spDir := [][]int{}, 0, [][]int{
		[]int{0, 1},  // Right
		[]int{1, 0},  // Down
		[]int{0, -1}, // Left
		[]int{-1, 0}, // Up
	}
	res = append(res, []int{r0, c0})
	for i := 0; len(res) < R*C; i++ {
		for j := 0; j < i/2+1; j++ {
			r0 += spDir[round%4][0]
			c0 += spDir[round%4][1]
			if 0 <= r0 && r0 < R && 0 <= c0 && c0 < C {
				res = append(res, []int{r0, c0})
			}
		}
		round++
	}
	return res
}