The Maze II — DSA-30

The Maze II medium

Description

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 won’t stop rolling until hitting a wall. When the ball stops, it could choose the next direction.

Given the maze, the ball’s start position, and the destination, return the shortest distance for the ball to stop at the destination. If the ball cannot stop at the destination, return -1.

The distance is the number of empty spaces traveled (not including the start cell, including the destination cell).

Examples

> Case 1:
    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 optimal path: left → down → left → down → right → down
 
> Case 2:
    start = [0,4], destination = [3,2]
    Output: -1
    # destination [3,2] is not a stopping cell from any rolling direction

Constraints

1 <= rows, cols <= 100
start.length == destination.length == 2
The ball and destination exist in empty spaces.

State design

This is NOT a plain BFS problem, because a single “move” can span many cells. From a stopping point, the ball rolls in one direction until it hits a wall — that’s one edge in the graph, with weight equal to the number of cells rolled.

The graph:

Vertices = cells where the ball can stop (every empty cell, plus the start).
Edges = from cell c, in each of 4 directions, roll until you hit a wall. The destination of that roll is one neighbor in the graph; the edge weight is the number of cells rolled.

Now it’s a weighted graph with non-negative weights → Dijkstra.

Code

Analysis

Time: O(m · n · max(m, n) · log(m · n)) — Dijkstra on m · n vertices, each “roll” is O(max(m, n)).
Space: O(m · n).

⚠️

Why plain BFS doesn’t work here. BFS assumes every edge has weight 1. In this problem, edges have variable weights (number of cells rolled). BFS would count “number of stops,” not “number of cells traveled” — different problem (that’s The Maze version 1).

Same skin

The Maze (version 1) — same rolling, but ask whether destination is reachable. BFS suffices.
The Maze III — same rolling, return the path itself as a string (with tie-breaking on lexicographic order). Dijkstra with parent + direction tracking.
Network Delay Time — single source Dijkstra on a regular graph.

Swim in Rising Water Overview