909. Snakes and Ladders

Problem

On an N x N board, the numbers from 1 to N*N are written boustrophedonically starting from the bottom left of the board, and alternating direction each row.  For example, for a 6 x 6 board, the numbers are written as follows:

You start on square 1 of the board (which is always in the last row and first column).  Each move, starting from square x, consists of the following:

• You choose a destination square S with number x+1, x+2, x+3, x+4, x+5, or x+6, provided this number is <= N*N.
  • (This choice simulates the result of a standard 6-sided die roll: ie., there are always at most 6 destinations, regardless of the size of the board.)
• If S has a snake or ladder, you move to the destination of that snake or ladder. Otherwise, you move to S.

A board square on row r and column c has a "snake or ladder" if board[r][c] != -1.  The destination of that snake or ladder is board[r][c].

Note that you only take a snake or ladder at most once per move: if the destination to a snake or ladder is the start of another snake or ladder, you do not continue moving.  (For example, if the board is [[4,-1],[-1,3]], and on the first move your destination square is 2, then you finish your first move at 3, because you do not continue moving to 4.)

Return the least number of moves required to reach square N*N.  If it is not possible, return -1.

Example 1:

Input:[
[-1,-1,-1,-1,-1,-1],
[-1,-1,-1,-1,-1,-1],
[-1,-1,-1,-1,-1,-1],
[-1,35,-1,-1,13,-1],
[-1,-1,-1,-1,-1,-1],
[-1,15,-1,-1,-1,-1]]
Output:4
Explanation:
At the beginning, you start at square 1 [at row 5, column 0].
You decide to move to square 2, and must take the ladder to square 15.
You then decide to move to square 17 (row 3, column 5), and must take the snake to square 13.
You then decide to move to square 14, and must take the ladder to square 35.
You then decide to move to square 36, ending the game.
It can be shown that you need at least 4 moves to reach the N*N-th square, so the answer is 4.

Note:

1. 2 <= board.length = board[0].length <= 20
2. board[i][j] is between 1 and N*N or is equal to 1.
3. The board square with number 1 has no snake or ladder.
4. The board square with number N*N has no snake or ladder.

Problem Summary

On an N x N board, squares are numbered from 1 to N*N, starting from the bottom-left corner and alternating direction each row. For the board at row r and column c, numbered according to the above method, a square may contain a "snake" or "ladder"; if board[r][c] != -1, the destination of that snake or ladder is board[r][c]. The player starts from square 1 on the board (always in the last row and first column). On each turn, the player starts from the current square x and moves according to the following requirements: choose a target square:

• Choose one target square from the squares numbered x+1, x+2, x+3, x+4, x+5, or x+6, with the target square's number <= N*N. This choice simulates rolling a die; regardless of the board size, your destination range can only be within the interval [x+1, x+6].
• Move the player: if the target square S contains a snake or ladder, then the player is moved to the destination of that snake or ladder. Otherwise, the player is moved to the target square S.

Note that during each move, the player can take at most one snake or ladder: even if the destination is the start of another snake or ladder, you will not continue moving. Return the minimum number of moves required to reach square N*N; if it is impossible, return -1.

Solution Ideas

• This problem can be abstracted as finding the shortest path from the starting point with index 1 to the ending point with index N^2 in a directed graph. Use breadth-first search. The board can be abstracted into a directed graph containing N^2 nodes. For each node x, if there is no snake or ladder on x+i (1 ≤ i ≤ 6), add a directed edge from x to x+i; otherwise, let the destination of the snake or ladder be y, and add a directed edge from x to y. Then solve it using the shortest path approach. Time complexity is O(n^2), and space complexity is O(n^2).
• The indices on the board in this problem are serpentine, so coordinate conversion is needed when traversing the next point. The specific method depends on the parity of the row: for even-numbered rows, indices go from left to right; for odd-numbered rows, indices go from right to left. See the getRowCol() function for the specific implementation.

Code

package leetcode

type pair struct {
	id, step int
}

func snakesAndLadders(board [][]int) int {
	n := len(board)
	visited := make([]bool, n*n+1)
	queue := []pair{{1, 0}}
	for len(queue) > 0 {
		p := queue[0]
		queue = queue[1:]
		for i := 1; i <= 6; i++ {
			nxt := p.id + i
			if nxt > n*n { // Out of bounds
				break
			}
			r, c := getRowCol(nxt, n) // Get the row and column for the next step
			if board[r][c] > 0 {      // There is a snake or ladder
				nxt = board[r][c]
			}
			if nxt == n*n { // Reached the destination
				return p.step + 1
			}
			if !visited[nxt] {
				visited[nxt] = true
				queue = append(queue, pair{nxt, p.step + 1}) // Expand a new state
			}
		}
	}
	return -1
}

func getRowCol(id, n int) (r, c int) {
	r, c = (id-1)/n, (id-1)%n
	if r%2 == 1 {
		c = n - 1 - c
	}
	r = n - 1 - r
	return r, c
}