Problem Description

You have a maze represented as a 2D grid where:

• 0 represents an empty space (the ball can pass through)
• 1 represents a wall (the ball cannot pass through)

A ball is placed at a starting position in the maze. The ball follows these movement rules:

1. The ball can roll in four directions: up, down, left, or right
2. Once the ball starts rolling in a direction, it keeps rolling until it hits a wall
3. When the ball hits a wall, it stops at the last empty space before the wall
4. After stopping, the ball can choose a new direction to roll

Given:

• A maze of size m x n
• A starting position start = [start_row, start_col]
• A destination position destination = [destination_row, destination_col]

Your task is to find the shortest distance (measured in number of empty spaces traveled) for the ball to reach the destination position. The distance count:

• Excludes the starting position
• Includes the destination position
• Counts every empty space the ball rolls through

If it's impossible for the ball to stop at the destination, return -1.

Important Note: The borders of the maze are considered walls, so the ball will always stop when reaching the edge of the maze.

Example: If a ball starts at position [0,4] and rolls left, passing through positions [0,3], [0,2], [0,1] before hitting a wall at column 0, the ball stops at [0,1] and has traveled a distance of 3.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The maze can be viewed as a graph where each empty cell is a node, and edges exist between cells that the ball can travel between (following the rolling rules).

Is it a tree?

• No: The maze graph contains cycles - the ball can potentially return to previously visited positions by taking different paths.

Is the problem related to directed acyclic graphs?

• No: The graph representation of possible ball movements contains cycles, not a DAG.

Is the problem related to shortest paths?

• Yes: We need to find the shortest distance (minimum number of spaces traveled) for the ball to reach the destination.

Is the graph weighted?

• Yes: Each edge has a weight representing the distance traveled when the ball rolls from one stopping point to another. When the ball rolls from one position until it hits a wall, the weight is the number of spaces it travels.

Dijkstra's Algorithm

• Yes: Since we have a weighted graph and need to find the shortest path, Dijkstra's algorithm is appropriate.

Conclusion: The flowchart suggests using Dijkstra's Algorithm for this problem. However, the provided solution uses a modified BFS approach that tracks distances, which is essentially implementing Dijkstra's algorithm concept. The solution maintains a distance matrix dist to track the shortest distance to reach each position, and uses a queue to explore positions in order of their distances. This is why the solution uses DFS-like exploration (rolling until hitting a wall) combined with BFS queue management to find the shortest path in this weighted graph scenario.

Intuition

The key insight is recognizing that this isn't a standard maze problem where we move one cell at a time. The ball's rolling behavior creates a unique challenge: once it starts rolling, it continues until hitting a wall. This means we're not exploring individual cells, but rather stopping points where the ball comes to rest.

Think of it this way: instead of a grid where we can move to any adjacent cell, we have a graph where nodes are "valid stopping positions" and edges represent "rolling paths" between these positions. The weight of each edge is the number of cells traveled during that roll.

Why can't we use simple BFS? In standard BFS, we assume each move has the same cost (usually 1). But here, rolling from one stopping point to another can cover different distances. Rolling left might travel 3 cells before hitting a wall, while rolling down might travel 5 cells. These different distances make it a weighted graph problem.

The natural approach is to track the minimum distance to reach each possible stopping position. We start from the initial position with distance 0, then explore all four directions:

1. Roll in each direction until hitting a wall
2. Calculate the total distance to reach that new stopping point
3. If this distance is better than what we've found before, update it and continue exploring from there

This is essentially Dijkstra's algorithm in disguise. We're maintaining a distance array dist[i][j] that stores the shortest distance to reach position (i, j) as a stopping point. We keep exploring positions, always updating distances when we find a shorter path, until we've explored all reachable positions.

The beauty of this approach is that it guarantees we find the shortest path because we're systematically exploring all possible rolling sequences while keeping track of the minimum distance to each stopping point.

Learn more about Depth-First Search, Breadth-First Search, Graph, Shortest Path and Heap (Priority Queue) patterns.

Solution Approach

The implementation uses a modified BFS with distance tracking to find the shortest path. Let's walk through the key components:

Data Structures:

• deque: A queue to store positions to be explored
• dist: A 2D array initialized with inf to track the minimum distance to reach each cell as a stopping point

Initialization:

dist[si][sj] = 0  # Starting position has distance 0
q = deque([(si, sj)])  # Add start position to queue

Main Algorithm:

1. Process each position from the queue:

   • Pop a position (i, j) from the queue
   • This represents a stopping point where the ball has come to rest

2. Explore all four directions using pairwise(dirs):

   • dirs = (-1, 0, 1, 0, -1) cleverly encodes the four directions
   • pairwise(dirs) generates pairs: (-1, 0), (0, 1), (1, 0), (0, -1) representing up, right, down, left

3. Simulate rolling in each direction:

   x, y, k = i, j, dist[i][j]  # Start from current position with current distance
   while 0 <= x + a < m and 0 <= y + b < n and maze[x + a][y + b] == 0:
       x, y, k = x + a, y + b, k + 1

   • Keep rolling while the next cell is valid and empty
   • Increment distance k for each cell traveled
   • Stop when hitting a wall or boundary

4. Update distance if a shorter path is found:

   if k < dist[x][y]:
       dist[x][y] = k
       q.append((x, y))

   • Only update and re-explore if we found a better path
   • This ensures we don't get stuck in infinite loops

5. Return the result:

   • Check dist[di][dj] for the destination
   • Return -1 if it's still inf (unreachable)
   • Otherwise return the shortest distance found

Why this works:

The algorithm essentially performs a relaxation process similar to Dijkstra's algorithm. By only adding positions to the queue when we find a shorter path, we ensure that:

• Each position is processed with increasingly better distances
• We eventually find the optimal distance to all reachable positions
• The destination's distance converges to the minimum possible value

The key insight is that we're not tracking distances to every cell, but only to cells where the ball can stop (after rolling and hitting a wall). This significantly reduces the search space while still guaranteeing the shortest path.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Given:

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]

Step-by-step execution:

Initialization:

• Create dist array (5x5) filled with inf
• Set dist[0][4] = 0 (starting position)
• Queue: [(0,4)]

Round 1: Process position (0,4)

• Current distance: 0
• Try all four directions:
  • Up: Can't move (boundary)
  • Right: Can't move (boundary)
  • Down: Roll from (0,4) → (1,4) → (2,4) → stop at (2,4) (hits wall at row 3)
    • Distance: 0 + 2 = 2
    • Update dist[2][4] = 2, add (2,4) to queue
  • Left: Roll from (0,4) → (0,3) → (0,2) → stop at (0,1) (hits wall at column 2)
    • Distance: 0 + 3 = 3
    • Update dist[0][1] = 3, add (0,1) to queue
• Queue: [(2,4), (0,1)]

Round 2: Process position (2,4)

• Current distance: 2
• Try all four directions:
  • Up: Roll back to (0,4) - distance 4, but dist[0][4] = 0 < 4, skip
  • Right: Can't move (boundary)
  • Down: Can't move (wall immediately below)
  • Left: Roll from (2,4) → (2,3) → (2,2) → (2,1) → stop at (2,0) (hits boundary)
    • Distance: 2 + 4 = 6
    • Update dist[2][0] = 6, add (2,0) to queue
• Queue: [(0,1), (2,0)]

Round 3: Process position (0,1)

• Current distance: 3
• Try all four directions:
  • Up: Can't move (boundary)
  • Right: Roll back to (0,4) - distance 6, but dist[0][4] = 0 < 6, skip
  • Down: Roll from (0,1) → (1,1) → (2,1) → stop at (2,1) (hits wall at row 3)
    • Distance: 3 + 2 = 5
    • Update dist[2][1] = 5, add (2,1) to queue
  • Left: Roll to (0,0) (hits boundary)
    • Distance: 3 + 1 = 4
    • Update dist[0][0] = 4, add (0,0) to queue
• Queue: [(2,0), (2,1), (0,0)]

Continue processing...

After several more rounds, we eventually reach position (4,4) through the following path:

• (0,4) → (2,4) [distance: 2]
• (2,4) → (2,0) [distance: 6]
• (2,0) → (4,0) [distance: 8]
• (4,0) → (4,4) [distance: 12]

Final Result: dist[4][4] = 12

The algorithm finds that the shortest distance from start (0,4) to destination (4,4) is 12 empty spaces traveled. Note how the ball must take a winding path due to the walls, and how we only track distances to positions where the ball can actually stop (after hitting a wall).

Solution Implementation

Time and Space Complexity

Time Complexity: O(m * n * max(m, n))

The algorithm uses BFS with a deque to explore the maze. In the worst case:

• Each cell (i, j) in the maze can be visited multiple times (when a shorter distance is found)
• There are m * n cells total
• For each cell, we explore 4 directions
• In each direction, the ball rolls until it hits a wall, which takes at most max(m, n) steps
• While a cell could theoretically be added to the queue multiple times, the distance check if k < dist[x][y] ensures we only process improving paths
• In the worst case, each cell could be updated O(m * n) times (once from each other cell)

Therefore, the overall time complexity is O(m * n * max(m, n)).

Space Complexity: O(m * n)

The space is used for:

• The dist matrix: O(m * n) to store the minimum distance to each cell
• The deque q: In the worst case, it could contain all cells, which is O(m * n)
• Other variables like dirs and loop variables: O(1)

The total space complexity is O(m * n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Confusing Cell Distance vs. Path Distance

The Problem: A common mistake is treating this like a standard BFS where we track whether we've visited each cell. Students often write code like:

visited = set()
visited.add((start_row, start_col))
# ... in the loop:
if (next_row, next_col) not in visited:
    visited.add((next_row, next_col))
    queue.append((next_row, next_col))

This fails because the ball can reach the same stopping position via different paths with different distances. Using a simple visited set prevents us from finding shorter paths to the same position.

The Solution: Use a distance matrix instead of a visited set. Only re-process a position if we've found a shorter path to it:

if steps < distance[next_row][next_col]:
    distance[next_row][next_col] = steps
    queue.append((next_row, next_col))

Pitfall 2: Incorrect Rolling Simulation

The Problem: Students often make mistakes in the rolling logic, such as:

# Wrong: Checking the current position instead of the next
while 0 <= next_row < rows and 0 <= next_col < cols and maze[next_row][next_col] == 0:
    next_row += delta_row
    next_col += delta_col
    steps += 1

This causes the ball to roll through walls because we're checking if the current position is valid, not if the next position would be valid.

The Solution: Always check the NEXT position before moving:

while (0 <= next_row + delta_row < rows and 
       0 <= next_col + delta_col < cols and 
       maze[next_row + delta_row][next_col + delta_col] == 0):
    next_row += delta_row
    next_col += delta_col
    steps += 1

Pitfall 3: Not Understanding When the Ball Can Stop

The Problem: A critical misunderstanding is thinking the ball can stop at any empty cell. Students might check if the ball passes through the destination:

# Wrong approach
while rolling:
    if (next_row, next_col) == (dest_row, dest_col):
        return steps  # Can't just stop here!

The ball can ONLY stop when it hits a wall or boundary. It cannot stop in the middle of an empty corridor just because it reached the destination.

The Solution: Let the ball complete its roll in each direction, then check if the stopping position matches the destination:

# Roll until hitting a wall
while (can_continue_rolling):
    # keep rolling
  
# After stopping, check if this is a valid stopping position
if steps < distance[next_row][next_col]:
    # Process this stopping position

Pitfall 4: Initializing Distance Incorrectly

The Problem: Forgetting to set the starting position's distance to 0:

distance = [[float('inf')] * cols for _ in range(rows)]
# Forgot: distance[start_row][start_col] = 0

This causes the algorithm to never find valid paths because all distances remain infinite.

The Solution: Always initialize the starting position's distance to 0:

distance = [[float('inf')] * cols for _ in range(rows)]
distance[start_row][start_col] = 0  # Critical initialization