Rolling Ball Shortest Distance to Destination
A warehouse ball rolls until it hits a wall, only then can it change direction. Given a maze, start, and destination, find the shortest distance the ball travels to stop exactly at the destination.
Problem
Given an m x n maze (0 = empty, 1 = wall), a start and a destination, a ball rolls up/down/left/right and does not stop until hitting a wall. Return the shortest distance (number of empty cells traversed) for the ball to stop at the destination, or -1 if impossible.
Input
maze: 2D 0/1 grid; start: [r,c]; destination: [r,c]. Both start and destination are empty cells.
Output
An integer shortest distance, or -1 if the ball cannot stop at the destination.
Constraints
- m == maze.length, n == maze[0].length
- 1 <= m, n <= 100
- The borders are walls implicitly via grid bounds; the ball stops at walls or edges.
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
One shortest stopping route covers 12 cells of travel.
Example 2
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
-1
The ball cannot stop on a cell it only rolls through.