题目
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.
解题思路
DFS遍历迷宫，注意每次移动只能走到障碍物才可以进行下一次移动
代码
class Solution:
def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
m, n, visit = len(maze), len(maze[0]), set()
directions = [(1, 0), (-1, 0), (0, -1), (0, 1)]
stack = [start]
while stack:
curx, cury = stack.pop()
if [curx, cury] == destination:
return True
for dirx, diry in directions:
tx, ty = curx, cury
while 0 <= tx + dirx < m and 0 <= ty + diry < n and not maze[tx + dirx][ty + diry]:
tx, ty = tx + dirx, ty + diry
if (tx, ty) not in visit:
visit.add((tx, ty))
stack.append((tx, ty))
return False
