Problem Description

You are given a maze represented as an m x n matrix where:

• Empty cells are marked with '.'
• Walls are marked with '+'

You start at a given entrance position entrance = [entrance_row, entrance_col] inside the maze.

Your task is to find the shortest path from the entrance to the nearest exit. An exit is defined as any empty cell ('.') that is located at the border of the maze (first/last row or first/last column). Note that the entrance itself doesn't count as an exit.

You can move one step at a time in four directions: up, down, left, or right. However:

• You cannot move into walls ('+')
• You cannot move outside the maze boundaries

Return the minimum number of steps needed to reach the nearest exit from the entrance. If no path to an exit exists, return -1.

For example, if you start at position [1, 2] in a maze and the nearest exit is 3 steps away at the border, you would return 3. If you're surrounded by walls and cannot reach any border, you would return -1.

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 is a node, and edges connect adjacent empty cells that we can move between.

Is it a tree?

• No: The maze is not a tree structure. It's a grid graph where cells can have multiple paths between them and may contain cycles.

Is the problem related to directed acyclic graphs?

• No: The maze is an undirected graph (we can move in all four directions), and it may contain cycles.

Is the problem related to shortest paths?

• Yes: We need to find the shortest path from the entrance to the nearest exit.

Is the graph Weighted?

• No: Each move from one cell to another has the same cost (1 step). All edges have equal weight.

BFS

• Yes: Since we have an unweighted graph and need to find the shortest path, BFS is the appropriate algorithm.

Conclusion: The flowchart suggests using BFS (Breadth-First Search) for finding the shortest path from the entrance to the nearest exit in an unweighted maze. BFS guarantees finding the shortest path in unweighted graphs because it explores nodes level by level, ensuring that when we first reach an exit, it's via the shortest possible path.

Intuition

When we need to find the shortest path in a maze, we should think about how we would explore it systematically. If we were physically in the maze, we'd want to explore all positions that are 1 step away from our starting point first, then all positions that are 2 steps away, then 3 steps away, and so on. This level-by-level exploration ensures that the first time we reach an exit, we've found it via the shortest possible route.

This is exactly what BFS does - it explores nodes in order of their distance from the starting point. We start at the entrance and expand outward like ripples in water, checking all cells at distance 1, then distance 2, and so forth.

The key insight is that since each move costs the same (1 step), we don't need complex algorithms like Dijkstra's. BFS naturally handles this unweighted shortest path problem. When we first encounter a cell that's on the border of the maze (and is empty), we know we've found the nearest exit because BFS guarantees we've explored all closer cells first.

To implement this, we use a queue to maintain the order of exploration. We mark visited cells (by changing '.' to '+' in the solution) to avoid revisiting them and getting stuck in cycles. The algorithm terminates either when we find an exit (return the number of steps) or when we've explored all reachable cells without finding an exit (return -1).

The entrance itself isn't considered an exit even if it's on the border, so we mark it as visited immediately and start our search from there. Each "layer" of BFS represents one additional step from the entrance, which is why we process the queue level by level and increment our step counter after each complete level.

Learn more about Breadth-First Search patterns.

Solution Approach

Following the BFS approach identified earlier, let's walk through the implementation step by step:

1. Initialize the BFS Setup

• Extract the dimensions of the maze: m (rows) and n (columns)
• Get the starting position from entrance: i, j = entrance
• Create a queue q using deque and add the entrance position (i, j) to it
• Mark the entrance as visited by setting maze[i][j] = "+" to prevent revisiting
• Initialize ans = 0 to track the number of steps

2. Level-by-Level BFS Traversal The key to finding the shortest path is processing the queue level by level:

• Before processing each level, increment ans += 1 (representing one more step from the entrance)
• Process all cells currently in the queue (this represents all cells at the same distance)
• For each cell (i, j) in the current level:
  • Check all four directions: [[0, -1], [0, 1], [-1, 0], [1, 0]] (left, right, up, down)
  • Calculate the new position: x, y = i + a, j + b

3. Validate and Process New Positions For each new position (x, y):

• Check if it's within bounds: 0 <= x < m and 0 <= y < n
• Check if it's an empty cell: maze[x][y] == "."
• If both conditions are met:
  • Check if it's an exit: If x == 0 or x == m - 1 or y == 0 or y == n - 1, this cell is on the border, so return ans immediately
  • If not an exit, add (x, y) to the queue for the next level
  • Mark as visited: maze[x][y] = "+" to avoid revisiting

4. Handle No Solution Case If the queue becomes empty (all reachable cells have been explored) and no exit was found, return -1.

The algorithm efficiently explores the maze level by level, guaranteeing that when an exit is found, it's reached via the shortest path. The time complexity is O(m × n) as we visit each cell at most once, and the space complexity is O(min(m, n)) for the queue in the worst case.

Example Walkthrough

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

Consider this 4×4 maze where we start at position entrance = [1, 2]:

maze = [
  ['+', '+', '.', '+'],
  ['.', '.', '.', '+'],
  ['+', '.', '.', '.'],
  ['+', '+', '+', '.']
]

Initial Setup:

• Start at position (1, 2)
• Mark entrance as visited: maze[1][2] = '+'
• Queue: [(1, 2)]
• Steps: ans = 0

Level 1 (ans = 1): Process position (1, 2) and explore its 4 neighbors:

• Up (0, 2): It's a '.' and on the border (row 0) → Found exit! Return 1

Let's consider a different example where the exit isn't immediately adjacent:

maze = [
  ['+', '+', '+', '+'],
  ['.', '.', '.', '+'],
  ['+', '.', '+', '.'],
  ['+', '+', '+', '.']
]
entrance = [1, 0]

Initial Setup:

• Start at (1, 0) - this is on the border but entrance doesn't count as exit
• Mark entrance: maze[1][0] = '+'
• Queue: [(1, 0)]
• Steps: ans = 0

Level 1 (ans = 1): Process (1, 0):

• Right (1, 1): Valid '.' → Add to queue, mark as '+'
• Other directions: walls or out of bounds
• Queue after level: [(1, 1)]

Level 2 (ans = 2): Process (1, 1):

• Right (1, 2): Valid '.' → Add to queue, mark as '+'
• Down (2, 1): Valid '.' → Add to queue, mark as '+'
• Queue after level: [(1, 2), (2, 1)]

Level 3 (ans = 3): Process (1, 2):

• All neighbors are walls or visited Process (2, 1):
• Right (2, 3): Valid '.' and on border (column 3) → Found exit! Return 3

The BFS guarantees we find the shortest path because we explore all cells at distance 1, then distance 2, then distance 3, finding the exit at the minimum distance of 3 steps.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × n)

In the worst case, the BFS algorithm needs to visit every cell in the maze exactly once. Each cell is added to the queue at most once (when it's first discovered and marked as visited by changing it to "+"), and each cell is processed at most once when it's dequeued. For each cell, we check at most 4 neighboring cells, which is a constant operation. Therefore, the total time complexity is O(m × n), where m is the number of rows and n is the number of columns in the maze.

Space Complexity: O(m × n)

The space complexity comes from two main sources:

1. The BFS queue q which in the worst case can contain O(m × n) cells (though typically it would be much less, containing only cells at the current BFS frontier)
2. The modification of the input maze array to mark visited cells with "+", which effectively uses the input array as a visited tracking mechanism

Even though we modify the input array in-place rather than creating a separate visited array, the queue can still grow to contain a significant portion of the cells in the maze, particularly in cases where the maze has large open areas. In the worst case scenario, the queue could contain up to O(m × n) elements, making the overall space complexity O(m × n).

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

Common Pitfalls

Pitfall 1: Incorrectly Counting the Entrance as an Exit

The Problem: A common mistake is checking if the current position is an exit before exploring its neighbors. Since we start at the entrance position, if the entrance happens to be on the border of the maze, the algorithm might incorrectly return 0 or 1 steps.

Why It Happens: The code processes the entrance position first in the queue. If we check for exit conditions at the beginning of processing each cell rather than when discovering new cells, we might mistakenly identify the entrance as an exit.

Incorrect Implementation:

while queue:
    for _ in range(len(queue)):
        current_row, current_col = queue.popleft()
      
        # WRONG: Checking if current position is an exit
        if current_row == 0 or current_row == rows - 1 or current_col == 0 or current_col == cols - 1:
            return steps  # This would return 0 if entrance is on border!
      
        # ... rest of the code

The Solution: Only check if a cell is an exit when we discover it as a neighbor, not when we process it from the queue. This ensures we never consider the entrance as an exit.

Pitfall 2: Incrementing Steps at the Wrong Time

The Problem: Placing steps += 1 inside the inner loop or after processing each cell instead of before processing each level leads to incorrect step counting.

Why It Happens: BFS processes cells level by level, where each level represents cells at the same distance from the start. The step counter should increment once per level, not once per cell.

Incorrect Implementation:

while queue:
    for _ in range(len(queue)):
        current_row, current_col = queue.popleft()
        steps += 1  # WRONG: This increments for each cell, not each level
      
        # ... rest of the code

The Solution: Increment steps once at the beginning of each while loop iteration, before processing all cells at the current level. This ensures all cells at the same distance share the same step count.

Pitfall 3: Not Capturing Queue Size Before Processing

The Problem: Using range(len(queue)) dynamically or not storing the queue size can lead to processing cells from different levels together.

Why It Happens: As we add new cells to the queue while processing the current level, the queue size changes. If we don't capture the initial size, we might process newly added cells in the same iteration.

Incorrect Implementation:

while queue:
    steps += 1
    # WRONG: Not processing level by level
    current_row, current_col = queue.popleft()
    # This processes one cell at a time, mixing levels

The Solution: Use for _ in range(len(queue)) where len(queue) is evaluated once at the beginning of each level. This ensures we only process cells that were in the queue at the start of this level, maintaining proper distance tracking.