The Maze II

A rolling ball starts at a source cell and keeps moving in one direction until it hits a wall. Return the minimum number of steps needed to stop at the destination. Pattern focus: Min-heap. Rolling movement breaks ordinary BFS because each move can cover a different distance.

Input Format

maze = grid, start = starting coordinate, destination = target coordinate

Output Format

minimum rolled distance to the destination, or -1

Constraints

  • 1 <= rows, cols <= 100
  • maze contains 0 for open and 1 for wall

Examples

Example 1:

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:

12

Explanation:

This is a classic rolling-ball shortest path case.

Example 2:

Input:

maze = [[0,0],[0,0]]
start = [0,0]
destination = [1,1]

Output:

-1

Explanation:

The ball cannot stop exactly at the destination.

Example 3:

Input:

maze = [[0,0,0],[0,0,0],[0,0,0]]
start = [0,0]
destination = [0,2]

Output:

2

Explanation:

The ball rolls straight to the destination and stops there.

Loading...
The Maze II - Shortest Path DSA Problem