# 490 The Maze

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 = [startrow, startcol]` and `destination = [destinationrow, destinationcol]`, 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:

``````# # # # # # #
# _ _ # _ O #
# _ _ _ _ _ #
# _ _ _ # _ #
# # # _ # # #
# _ _ _ _ M #
# # # # # # #

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:

``````# # # # # # #
# _ _ # _ O #
# _ _ _ _ _ #
# _ _ _ # _ #
# # # M # # #
# _ _ _ _ _ #
# # # # # # #

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 <= startrow, destinationrow <= m`
• `0 <= startcol, destinationcol <= 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.
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 `````` ``````class Solution: def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool: m = len(maze) n = len(maze) def dfs(row: int, col: int) -> bool: if visited[row][col]: return False if row == destination and col == destination: return True visited[row][col] = True left, right = col - 1, col + 1 top, bottom = row - 1, row + 1 # move right while right < n and maze[row][right] == 0: right += 1 if dfs(row, right - 1): return True # move left while left >= 0 and maze[row][left] == 0: left -= 1 if dfs(row, left + 1): return True # move up while top >= 0 and maze[top][col] == 0: top -= 1 if dfs(top + 1, col): return True # move down while bottom < m and maze[bottom][col] == 0: bottom += 1 if dfs(bottom - 1, col): return True return False visited = [[False] * n for _ in range(m)] return dfs(start, start)``````