DSA problem
The Maze II
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 will not 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 = [start_row, start_col] and destination = [destination_row, destination_col], return the shortest distance for the ball to stop at the destination (the total number of empty spaces traveled). If the ball cannot stop at the destination, return -1.
The key insight is that the ball does not stop at every cell — it only stops when it hits a wall or the edge of the maze. So the graph nodes are stop positions and the edges are roll segments. Each edge has a weight equal to the number of cells the ball travels along that segment, which is generally greater than 1.
Because edge weights are non-uniform positive integers, plain BFS is incorrect: a shorter path in number of cells is not necessarily a shorter path in number of stops. Dijkstra's algorithm with a min-heap keyed by total distance is the natural fit.
Pop the stop position with the smallest accumulated distance, then for each of the 4 directions roll the ball until it hits a wall, counting how many cells it traversed. The neighbour is the cell where it stopped; the edge weight is the count of cells rolled over. Use a distance matrix to prune: only enqueue if the new total distance is better than the previously recorded one. Time is O(m * n * max(m, n) * log(m * n)) since each "rolling neighbour" takes O(m + n) time and each cell may be relaxed multiple times before being settled.
Examples
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]12maze = [[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]-1maze = [[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]-1Constraints
- m == maze.length
- n == maze[i].length
- 1 <= m, n <= 100
- maze[i][j] is 0 or 1.
- start.length == destination.length == 2
- maze[start_row][start_col] == 0 and maze[destination_row][destination_col] == 0
- The ball and destination exist on empty spaces.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.