KK's blog

每天积累多一些

0%

LeetCode 490 The Maze

Posted on Edited on Disqus:

LeetCode



There is a ball in a maze with empty spaces (represented as 0) and walls (represented as 1). The ball can go through the empty spaces by rolling up, down, left or right, but it won’t stop rolling until hitting a wall. When the ball stops, it could choose the next direction.

Given the m x n maze, the ball’s start position and the destination, where start = [start<sub>row</sub>, start<sub>col</sub>] and destination = [destination<sub>row</sub>, destination<sub>col</sub>], return true if the ball can stop at the destination, otherwise return false.

You may assume that the borders of the maze are all walls (see examples).

Example 1:



Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4]
Output: true
Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right.


Example 2:



Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [3,2]
Output: false
Explanation: There is no way for the ball to stop at the destination. Notice that you can pass through the destination but you cannot stop there.


Example 3:

Input: maze = [[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]], start = [4,3], destination = [0,1]
Output: false


Constraints:

m == maze.length n == maze[i].length
1 <= m, n <= 100 maze[i][j] is 0 or 1.
start.length == 2 destination.length == 2
0 <= start<sub>row</sub>, destination<sub>row</sub> <= m 0 <= start<sub>col</sub>, destination<sub>col</sub> <= n
Both the ball and the destination exist in an empty space, and they will not be in the same position initially. The maze contains at least 2 empty spaces.

题目大意：

球在玉米迷宫上滚，当遇到边界或玉米会停下，停下后可以转任意方向。求能否停在目标上。

算法思路：

二维数组求目标第一时间想到用BFS，此题求能停下的点而不是所有点。所以属于一组节点作为一层的BFS，也就是说只有能停下的位置才算BFS的一层，才加入都队列，其他停不来的点均忽略。这是此题的难点。

注意事项：

  1. 属于一组节点作为一层的BFS，能停下的点才加入到queue。比标准模板多了Line 10 - 11. 停下包括边界和玉米(maze[x][y] == 1)
  2. 要滚回一步Line 12 - 15，因为line 10循环的终结状态为出界或玉米上。要滚回一步到空地上。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
	queue = collections.deque([(start[0], start[1])])
	visited = set([(start[0], start[1])])
	while queue:
		node = queue.popleft()
		if node[0] == destination[0] and node[1] == destination[1]:
			return True
		for _dx, _dy in OFFSETS:
			x, y = node[0], node[1]
			while 0 <= x < len(maze) and 0 <= y < len(maze[0]) and maze[x][y] == 0: # remember maze[x][y] == 0
				x, y = x + _dx, y + _dy
			if (x - _dx, y - _dy) in visited: # remember
				continue
			queue.append((x - _dx, y - _dy))
			visited.add((x - _dx, y - _dy))
	return False

算法分析：

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

Free mock interview