LeetCode 909 Snakes and Ladders

LeetCode

You are given an n x n integer matrix board where the cells are labeled from 1 to n<sup>2</sup> in a Boustrophedon style starting from the bottom left of the board (i.e. board[n - 1][0]) and alternating direction each row.

You start on square 1 of the board. In each move, starting from square curr, do the following:

Choose a destination square next with a label in the range [curr + 1, min(curr + 6, n<sup>2</sup>)]. This choice simulates the result of a standard 6-sided die roll: i.e., there are always at most 6 destinations, regardless of the size of the board.
If next has a snake or ladder, you must move to the destination of that snake or ladder. Otherwise, you move to next. The game ends when you reach the square n<sup>2</sup>.

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]. Squares 1 and n<sup>2</sup> do not have a snake or ladder.

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 follow the subsequent snake or ladder.

For example, suppose the board is [[-1,4],[-1,3]], and on the first move, your destination square is 2. You follow the ladder to square 3, but do not follow the subsequent ladder to 4.

Return the least number of moves required to reach the square n<sup>2</sup>. If it is not possible to reach the square, return -1.

Example 1:

Input: board = [[-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:
In 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 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.
This is the lowest possible number of moves to reach the last square, so return 4.

Example 2:

Input: board = [[-1,-1],[-1,3]]
Output: 1

Constraints: n == board.length == board[i].length
2 <= n <= 20 grid[i][j] is either -1 or in the range [1, n<sup>2</sup>].
* The squares labeled 1 and n<sup>2</sup> do not have any ladders or snakes.

题目大意：

二维版上每格label从1到n^2, 从左到右或从右到左(梅花间竹)，从下到上。每次走1-6步，格上可能有梯子和蛇，梯子是快进，蛇是回退直接到达目标格。求从1到n^2所需要步数。始点和目标不含梯子和蛇。

BFS解题思路(推荐)：

求最值两个方法：DP和BFS。一开始考虑用DP，但状态很复杂，因为存在回退，这样回退后要重新计算回退之后的DP值。
由于此题没有方向性而且似jump game，所以考虑用DP。

解题步骤：

N/A

注意事项：

1. 题意：对于梯子和蛇，它不能停留在梯子和蛇的起点，只能够停在终点，所以梯子和蛇的起点到1的距离为无穷大。其实可以留在起点，比如一个格同时是蛇的终点和梯子的起点。题意表明不能在同一步中两次用梯子或蛇。
2. 根据上述题意，程序中对应是如碰到儿子中有梯子和蛇的起点，完全忽略它，立刻转换成终点，也就是不入列，不入visited，不计算距离，完全当其透明。开始犯的错误是将其入列，出列才计算梯子终点。此算法仍然可以满足上述题意，此时梯子的起点会被加入到visited和distance，queue中，因为它确实停在那里了。
3. visited在计算完梯子和蛇的终点后才处理，而不是进入for loop后
4. neighbor不能超过n，达不到目标返回-1
5. 另一个难点在label转成坐标从而查找是否有梯子和蛇

Python代码：

def snakesAndLadders(self, board: List[List[int]]) -> int:
	n = len(board) * len(board)
	queue = collections.deque([1])
	visited = set([1])
	distance = {1: 0}
	while queue:
		node = queue.popleft()
		if node == n:
			return distance[node]
		for neighbor in range(node + 1, node + 7):
			if neighbor > n:  # remember
				continue

			board_x, board_y = self.get_board_cell(len(board), neighbor)
			dest_label = board[board_x][board_y]
			next_step = dest_label if dest_label != -1 else neighbor

			if next_step in visited: # remember to put it after dest_label
				continue

			queue.append(next_step)
			visited.add(next_step)
			distance[next_step] = distance[node] + 1
	return -1  # remember

def get_board_cell(self, n, label): # 6, 6
	label -= 1 # rememeber
	row_id = label // n # 0
	col_id = label % n
	return n - 1 - row_id, n - 1 - col_id if row_id % 2 == 1 else col_id

算法分析：

时间复杂度为O(n2)，空间复杂度O(n2)

另一种优化是只入最远的节点和蛇梯子的终点，类似于jump两种，类似于jump game。

Python代码：

def snakesAndLadders(self, board: List[List[int]]) -> int:
    n = len(board) * len(board)
	queue = collections.deque([1])
	visited = set([1])
	distance = {1: 0}
	while queue:
		node = queue.popleft()
		if node == n:
			return distance[node]
		max_non_jump = node
		for neighbor in range(node + 1, node + 7):
			if neighbor > n:  # remember
				continue

			board_x, board_y = self.get_board_cell(len(board), neighbor)
			dest_label = board[board_x][board_y]
			next_step = dest_label if dest_label != -1 else neighbor

			if next_step in visited:  # remember to put it after dest_label
				continue
			if dest_label != -1:
				queue.append(next_step)
				visited.add(next_step)
				distance[next_step] = distance[node] + 1
			else:
				max_non_jump = next_step
		if max_non_jump in visited:  # remember to put it after dest_label
			continue
		queue.append(max_non_jump)
		visited.add(max_non_jump)
		distance[max_non_jump] = distance[node] + 1
	return -1  # remember

def get_board_cell(self, n, label): # 6, 6
	label -= 1 # rememeber
	row_id = label // n # 0
	col_id = label % n
	return n - 1 - row_id, n - 1 - col_id if row_id % 2 == 1 else col_id

算法分析：

时间复杂度为O(n2/6)，空间复杂度O(n2/6)

---

DP算法II解题思路(不推荐)：

非常容易错，且效率更低，需要回退重新计算dp值。 dp[i] + 1 < dp[dest_label]保证不会在无限回退，i = dest_label - 1要在break前做，而不是更前，否二影响dp[dest_label]计算

Python代码：

def snakesAndLadders_dp(self, board: List[List[int]]) -> int:
	N = len(board) * len(board) + 1
	dp = [float('inf') for _ in range(N)]
	dp[1] = 0 # remember
	# i is label id
	i = 1
	# for i in range(2, N):
	while i < N:
		for k in range(1, 7):
			if i + k < N:
				board_x, board_y = self.get_board_cell(len(board), i + k)
				dest_label = board[board_x][board_y]
				next_step = dest_label if dest_label != -1 else i + k
				if dest_label != -1:
					if dest_label < i and dp[i] + 1 < dp[dest_label]: # remember 
						dp[dest_label] = min(dp[dest_label], dp[i] + 1)
						i = dest_label - 1 # remember to assign at the end
						break

				dp[next_step] = min(dp[next_step], dp[i] + 1) # remember + 1 inside min
		i += 1
	return dp[-1] if dp[-1] != float('inf') else -1 # remember

算法分析：

时间复杂度为O(n2)，空间复杂度O(n2)