490.The Maze
Tags: [maze], [matrix], [graph], [DP], [memo], [top_to_bottom_dp], [direction], [DFS], [backtracking], [trick]
Com: {g}
Hard: [##]
Link: https://leetcode.com/problems/the-maze/#/description
There is a ball in a maze with empty spaces and walls. The ball can go through 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 ball's start position, the destination and the maze, determine whether the ball could stop at the destination.
The maze is represented by a binary 2D array. 1 means the wall and 0 means the empty space. You may assume that the borders of the maze are all walls. The start and destination coordinates are represented by row and column indexes.
Example 1
Input 1: a maze represented by a 2D array
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
Input 2: start coordinate (rowStart, colStart) = (0, 4)
Input 3: destination coordinate (rowDest, colDest) = (4, 4)
Output: true
Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right.
Example 2
Input 1: a maze represented by a 2D array
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
Input 2: start coordinate (rowStart, colStart) = (0, 4)
Input 3: destination coordinate (rowDest, colDest) = (3, 2)
Output: false
Explanation: There is no way for the ball to stop at the destination.
Note:
- There is only one ball and one destination in the maze.
- Both the ball and the destination exist on an empty space, and they will not be at the same position initially.
- The given maze does not contain border (like the red rectangle in the example pictures), but you could assume the border of the maze are all walls.
- The maze contains at least 2 empty spaces, and both the width and height of the maze won't exceed 100.
Solution: DFS, Backtracking, DP, Memo
class Solution(object):
def hasPath(self, maze, start, destination):
"""
:type maze: List[List[int]]
:type start: List[int]
:type destination: List[int]
:rtype: bool
"""
if not maze or not maze[0]:
return False
rows, cols = len(maze), len(maze[0])
visited = {}
memo = {}
# iterate top, left, bottom, right
for d in ((-1, 0), (0, -1), (1, 0), (0, 1)):
if self.dfs(maze, rows, cols, start[0], start[1], destination[0], destination[1], d, visited, memo):
return True
return False
def dfs(self, maze, rows, cols, row, col, d_row, d_col, direction, visited, memo):
# base case
if row == d_row and col == d_col:
r, c = row + direction[0], col + direction[1]
if not (0 <= r < rows and 0 <= c < cols and maze[r][c] == 0):
return True
state = '{}:{}:{}:{}'.format(row, col, direction[0], direction[1])
if state in memo:
return memo[state]
visited[state] = True
r, c = row + direction[0], col + direction[1]
if 0 <= r < rows and 0 <= c < cols and maze[r][c] == 0:
next_state = '{}:{}:{}:{}'.format(r, c, direction[0], direction[1])
if visited.get(next_state, False):
visited[state] = False
memo[state] = False
return False
else:
if self.dfs(maze, rows, cols, r, c, d_row, d_col, direction, visited, memo):
# we don't need to set visited[state] back to False here,
# because we use dfs not for traversing all possible path,
# what we want is that once find the True, then we can terminate.
memo[state] = True
return True
else:
# the ball hits wall and stop.
# iterate remaining directions:
for d in ((-1, 0), (0, -1), (1, 0), (0, 1)):
if d == direction:
continue
r, c = row + d[0], col + d[1]
next_state = '{}:{}:{}:{}'.format(r, c, d[0], d[1])
if 0 <= r < rows and 0 <= c < cols and maze[r][c] == 0 and not visited.get(next_state, False):
if self.dfs(maze, rows, cols, r, c, d_row, d_col, d, visited, memo):
# we don't need to set visited[state] back to False here,
# because we use dfs not for traversing all possible path,
# what we want is that once find the True, then we can terminate.
memo[state] = True
return True
visited[state] = False
memo[state] = False
return False
Revelation:
- The key point is the visited map is not just record row and col, it also need record the direction. Because different directions may pass the same (row, col).
- 可以用DP是因为，可以通过多种途径到达某个(row, col, direction), 例如一开始往左走和一开始往下走都可以到达某个(row, col, direction)，所以我们用memo记下当前state可以导致的结果，用来避免重复计算.
Note:
- Time complexity = O(rows * cols * 2 * 2) = O(rows * cols), because there are (rows * cols * 2 * 2) states, and each state only gets to be calculated once.