Mid/Senior
The Maze II
Given an m x n maze represented by a binary matrix maze, where 0 represents an empty space and 1 represents a wall, a ball starts at position start and needs to reach position destination.
The ball can roll in one of four directions: up, down, left, or right. Once it starts rolling in a direction, it continues moving until it hits a wall or the boundary of the maze. The ball can only choose a new direction after it stops.
The distance is the number of empty spaces traveled by the ball, excluding the starting position but including the destination position if reached.
Return the shortest distance for the ball to stop at destination. If the ball cannot stop at destination, return -1.
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
12The ball can stop at the destination with a shortest rolling distance of 12.
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
-1Although the ball can pass through the destination cell, 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 the ball and the destination exist in empty spaces, and they will not be at the same position initially