Mid/Senior
The Maze
There is a ball in a maze with empty spaces and walls. The maze is represented by an m x n binary matrix maze, where maze[i][j] == 0 means the cell is empty and maze[i][j] == 1 means the cell is a wall.
The ball starts at position start = [start_row, start_col] and wants to reach destination = [destination_row, destination_col]. The ball can roll in one of four directions: up, down, left, or right. However, once it starts rolling in a direction, it keeps rolling until it hits a wall or the boundary of the maze, and it stops on the cell immediately before the wall or boundary. Only after stopping can it choose a new direction.
Return true if the ball can stop at destination; otherwise, return false.
Example 1
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
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
trueThe ball can roll through a sequence of stopping points that eventually stops exactly at [4, 4].
Example 2
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
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
falseThe ball can pass over [3, 2], but it cannot stop there, so the destination is unreachable.
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[0], destination[0] < m
- 0 <= start[1], destination[1] < n
- Both
startanddestinationare empty spaces