Problem Description

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

• 0 represents an empty space
• 1 represents a wall

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

• It can roll in four directions: up, down, left, or right
• Once the ball starts rolling in a direction, it keeps rolling until it hits a wall
• When the ball hits a wall, it stops and can then 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]

You need to determine if it's possible for the ball to stop at the destination position.

Important notes:

• The ball must stop at the destination (not just pass through it)
• The borders of the maze are considered walls
• The ball can only stop when it hits a wall

For example, if the ball is rolling right, it will continue moving right through all empty spaces (0) until it reaches a wall (1) or the maze boundary, at which point it stops and can choose a new direction.

The function should return true if the ball can reach and stop at the destination, false otherwise.

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 represented as a graph where each empty cell (0) is a node, and edges exist between cells that the ball can roll between. The ball's movement creates paths through this graph.

Is it a tree?

• No: The maze is not a tree structure. It's a 2D grid where multiple paths can exist between positions, and cycles are possible (the ball can return to previously visited positions through different routes).

Is the problem related to directed acyclic graphs?

• No: The maze graph can have cycles - the ball can potentially return to a position it has already visited by taking a different path.

Is the problem related to shortest paths?

• No: We don't need to find the shortest path. We only need to determine if the ball can reach and stop at the destination, regardless of the path length.

Does the problem involve connectivity?

• No: While we need to check if we can reach the destination, this isn't a pure connectivity problem like finding connected components or checking if nodes belong to the same component.

Does the problem have small constraints?

• Yes: Maze problems typically have reasonable constraints (usually up to 100x100 or similar), making DFS/backtracking feasible without timeout issues.

DFS/backtracking?

• Yes: DFS is perfect for exploring all possible paths the ball can take. We need to explore each possible direction the ball can roll from each stopping position until we either find the destination or exhaust all possibilities.

Conclusion: The flowchart suggests using DFS/backtracking to explore all possible paths the ball can take through the maze, checking if any path leads to stopping at the destination position.

Intuition

The key insight is understanding how the ball moves - it doesn't stop at every cell like typical maze problems. Once the ball starts rolling in a direction, it keeps going until it hits a wall. This creates a unique graph structure where nodes are not individual cells, but rather stopping positions.

Think of it this way: when the ball is at a position, we have at most 4 choices (up, down, left, right). For each direction, we simulate the ball rolling continuously until it hits a wall or boundary. The position where it stops becomes a new node in our search space.

This naturally leads to a DFS approach because:

1. We need to explore all possible paths from the starting position
2. From each stopping position, we branch out to explore all 4 directions
3. We continue this exploration recursively until we either find the destination or exhaust all possibilities

The visited tracking is crucial here - we mark stopping positions as visited to avoid infinite loops. If the ball reaches a stopping position it has already visited, we know this path won't lead to a new solution.

Why DFS over BFS? Both would work, but DFS is simpler to implement for this problem. We don't need the shortest path (where BFS would shine), we just need to know if ANY path exists. DFS naturally explores one complete path before backtracking to try another, which is perfectly suited for this "can we reach the destination?" question.

The algorithm essentially builds a graph on-the-fly where:

• Nodes = stopping positions (where the ball hits a wall)
• Edges = the rolling motion between stopping positions
• Goal = check if destination node is reachable from start node

Solution Approach

The implementation uses DFS with a visited matrix to track which stopping positions we've already explored. Let's walk through the key components:

1. Visited Matrix Setup:

vis = [[False] * n for _ in range(m)]

We create a 2D boolean matrix matching the maze dimensions to track visited stopping positions. This prevents infinite loops when the ball revisits the same stopping point.

2. DFS Function Structure: The dfs(i, j) function explores all possible paths from position (i, j):

• First, it checks if this position was already visited. If yes, return immediately to avoid redundant exploration
• Mark the current position as visited: vis[i][j] = True
• Check if we've reached the destination: if [i, j] == destination

3. Rolling Simulation:

for a, b in [[0, -1], [0, 1], [1, 0], [-1, 0]]:
    x, y = i, j
    while 0 <= x + a < m and 0 <= y + b < n and maze[x + a][y + b] == 0:
        x, y = x + a, y + b
    dfs(x, y)

For each of the 4 directions (left, right, down, up):

• Initialize (x, y) to the current position
• Use a while loop to simulate the ball rolling in direction (a, b)
• The ball keeps rolling while:
  • The next position (x + a, y + b) is within bounds
  • The next position is an empty space (value is 0)
• When the loop exits, (x, y) is the stopping position
• Recursively call dfs(x, y) to explore from this new stopping position

4. Main Execution:

dfs(start[0], start[1])
return vis[destination[0]][destination[1]]

• Start the DFS from the initial position
• After DFS completes, check if the destination was visited
• If vis[destination[0]][destination[1]] is True, the ball can reach and stop at the destination

Why This Works: The algorithm systematically explores all reachable stopping positions from the start. By marking positions as visited, we ensure each stopping position is processed only once. If the destination becomes marked as visited during this exploration, it means there exists at least one valid path for the ball to reach and stop at the destination.

The time complexity is O(m*n*max(m,n)) where the extra factor accounts for the rolling simulation in each direction. The space complexity is O(m*n) for the visited matrix and recursion stack.

Example Walkthrough

Let's walk through a small example to illustrate how the DFS solution works.

Consider this maze:

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]

Where 0 = empty space, 1 = wall, S = start position (0,4), D = destination (4,4).

Visualized with S and D:

[0, 0, 1, 0, S]
[0, 0, 0, 0, 0]
[0, 0, 0, 1, 0]
[1, 1, 0, 1, 1]
[0, 0, 0, 0, D]

Step 1: Start DFS from position (0, 4)

• Mark (0, 4) as visited
• Try rolling in 4 directions:

Step 2: Rolling Left from (0, 4)

• Ball rolls: (0,4) → (0,3) → stops at (0,2) because maze[0][2] = 1 (wall)
• Call dfs(0, 2)
• Mark (0, 2) as visited, but it's not the destination
• From (0, 2), the ball can only roll down

Step 3: Rolling Down from (0, 2)

• Ball rolls: (0,2) → (1,2) → (2,2) → stops at (2,2) because maze[3][2] = 0 but maze[3][1] = 1 and maze[3][3] = 1 (surrounded by walls)
• Call dfs(2, 2)
• Mark (2, 2) as visited

Step 4: From (2, 2), try all directions

• Up: rolls back to (0, 2) - already visited, skip
• Down: can't move (wall at 3,2)
• Left: rolls to (2, 0) - stops at left boundary
• Right: rolls to (2, 3) - stops at wall

Step 5: Continue exploring from (2, 0)

• Mark (2, 0) as visited
• Roll down: goes to (4, 0)
• From (4, 0), roll right: (4,0) → (4,1) → (4,2) → (4,3) → (4,4)
• Ball stops at (4, 4) - this is our destination!

Step 6: Mark destination as visited

• vis[4][4] = True
• Return from recursive calls

Final Result: After DFS completes, we check vis[4][4] which is True, so the function returns true - the ball can reach the destination.

The key insight: The ball doesn't stop at every cell. When rolling from (4,0) to the right, it passes through (4,1), (4,2), and (4,3) without stopping, finally stopping at (4,4) when it hits the right boundary.

Solution Implementation

Time and Space Complexity

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

The algorithm uses DFS to explore all reachable positions in the maze. In the worst case:

• We visit each cell at most once due to the visited array, giving us O(m * n) cells to explore
• For each cell we visit, we simulate rolling the ball in 4 directions
• Each roll simulation can take up to O(max(m, n)) steps in the worst case (rolling from one end of the maze to the other)
• Therefore, the total time complexity is O(m * n * max(m, n))

Space Complexity: O(m * n)

The space complexity consists of:

• The visited array vis which uses O(m * n) space to track visited cells
• The recursive call stack for DFS, which in the worst case can go up to O(m * n) depth if we visit all cells in a chain
• Therefore, the total space complexity is O(m * n)

Common Pitfalls

Pitfall 1: Confusing Visited Positions - Rolling vs. Stopping

The Problem: A common mistake is marking positions as visited while the ball is rolling through them, rather than only marking the positions where the ball stops. This leads to incorrect results because the ball might need to pass through the same position multiple times in different directions.

Incorrect Implementation:

def dfs(row, col):
    if visited[row][col]:
        return
    visited[row][col] = True
  
    for delta_row, delta_col in directions:
        next_row, next_col = row, col
        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
            # WRONG: Marking intermediate positions as visited
            visited[next_row][next_col] = True
        dfs(next_row, next_col)

Why It's Wrong: Consider a simple maze where the ball needs to roll through position (2, 2) horizontally to reach (2, 4), then later roll through the same position (2, 2) vertically to reach the destination at (4, 2). If we mark (2, 2) as visited during the horizontal roll, the vertical path becomes blocked.

Correct Approach: Only mark positions as visited where the ball actually stops (when it hits a wall):

def dfs(row, col):
    if visited[row][col]:
        return
    visited[row][col] = True  # Only mark stopping position
  
    for delta_row, delta_col in directions:
        next_row, next_col = row, col
        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
            # No marking during rolling
        dfs(next_row, next_col)  # Only explore from stopping position

Pitfall 2: Incorrect Boundary Check in While Loop

The Problem: Using the wrong boundary check can cause index out of bounds errors or incorrect stopping positions.

Incorrect Implementation:

# WRONG: Checking current position instead of next position
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

Why It's Wrong: This checks if the current position is valid and empty, but then moves to the next position without verifying it. The ball could roll into a wall or out of bounds.

Correct Approach: 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

Pitfall 3: Not Handling the Case Where Start Equals Destination

The Problem: If the starting position is the same as the destination, the solution should return True only if the ball can move away and come back to stop at that position. Simply returning True immediately would be incorrect.

Incorrect Implementation:

def hasPath(maze, start, destination):
    if start == destination:
        return True  # WRONG: Assumes ball can stop without moving
    # ... rest of the code

Why It's Wrong: The ball might be in the middle of an open area where it cannot stop. It must hit a wall to stop, so even if start equals destination, we need to verify that the ball can actually stop at that position.

Correct Approach: Let the DFS algorithm handle this case naturally. The ball will explore all possible paths, and if it can return to the starting position as a valid stopping point, the algorithm will mark it as visited:

def hasPath(maze, start, destination):
    # No special case for start == destination
    dfs(start[0], start[1])
    return visited[destination[0]][destination[1]]

The algorithm correctly handles this because it only marks positions where the ball can actually stop (after hitting a wall).