Nearest Exit from Entrance in Maze: BFS Shortest Path

You are given an m x n matrix maze where each cell is either empty ('.') or a wall ('+'). You are also given the entrance as a [row, col] pair. An exit is any empty cell on the border of the maze that is not the entrance itself. Return the number of steps in the shortest path from the entrance to the nearest exit, or -1 if no such path exists.

This is LeetCode 1926: Nearest Exit from Entrance in Maze, and it is a textbook application of BFS on a grid. If you can solve this problem cleanly, you understand how BFS guarantees shortest paths in unweighted graphs.

Why this problem matters

Shortest path problems on grids come up constantly in interviews and real applications: game AI pathfinding, network routing, robot navigation. The core technique is always the same. Treat each cell as a node, treat each valid move to an adjacent cell as an edge, and run BFS. Because every edge has the same weight (one step), BFS finds the shortest path by definition.

What makes this problem interesting is the exit condition. You are not looking for a fixed target cell. You are looking for any empty cell on the border. That means BFS will naturally find the closest one first, because it processes cells in order of increasing distance. The moment you dequeue a border cell, you have your answer.

This pattern, BFS to the nearest cell satisfying some condition, shows up in problems like Rotting Oranges, Walls and Gates, and Shortest Path in Binary Matrix.

The approach: BFS on a grid

The algorithm works level by level:

1. Start by adding the entrance to the queue with distance 0. Mark it as visited.
2. For each cell in the current level, check all four neighbors (up, down, left, right).
3. If a neighbor is in bounds, is an empty cell, and has not been visited, add it to the queue.
4. Before adding a neighbor, check: is it on the border of the maze? If yes, return the current distance + 1.
5. If the queue empties without finding an exit, return -1.

The key detail is marking the entrance as visited (or turning it into a wall) so you never revisit it. The entrance is on the border, but it does not count as an exit. By marking it visited before BFS starts, you avoid accidentally returning distance 0.

from collections import deque

def nearest_exit(maze: list[list[str]], entrance: list[int]) -> int:
    rows, cols = len(maze), len(maze[0])
    r0, c0 = entrance
    maze[r0][c0] = "+"
    queue = deque([(r0, c0, 0)])

    while queue:
        r, c, dist = queue.popleft()
        for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and maze[nr][nc] == ".":
                if nr == 0 or nr == rows - 1 or nc == 0 or nc == cols - 1:
                    return dist + 1
                maze[nr][nc] = "+"
                queue.append((nr, nc, dist + 1))

    return -1

BFS guarantees the shortest path because it processes all cells at distance d before any cell at distance d + 1. The first time you reach a border cell, you know no shorter path exists. This is the fundamental property of BFS on unweighted graphs, and it is what separates BFS from DFS for shortest path problems. DFS might find an exit, but it could take a longer route to get there.

Complexity analysis

Time: Each cell is visited at most once. For each cell, we check four neighbors in O(1). Total work is O(m * n) where m is the number of rows and n is the number of columns.

Space: In the worst case, the queue can hold O(m * n) cells (imagine a maze with no walls). The visited marking is done in place by mutating the maze to "+", so no extra visited set is needed. If you cannot mutate the input, add a visited set of size O(m * n).

Edge cases to watch for

• No exit exists: every border cell is a wall, or the entrance is completely surrounded by walls. BFS exhausts the queue and returns -1.
• Entrance is surrounded: the entrance has no empty neighbors. The queue empties immediately. Return -1.
• Exit is adjacent to entrance: the entrance is on the border and an adjacent border cell is empty. BFS finds it at distance 1 on the first expansion.
• Large open maze: the entire maze is empty. BFS still works correctly, finding the nearest border cell. The queue grows to O(m * n) in the worst case.
• Single row or column: the maze is 1 x n or m x 1. Every empty cell is on the border. The nearest empty neighbor of the entrance is the answer.

The building blocks

This problem is built on two reusable pieces that appear across dozens of grid problems.

1. BFS level-by-level traversal

The pattern of expanding outward from a source, processing all cells at distance d before distance d + 1:

queue = deque([(start_r, start_c, 0)])
visited.add((start_r, start_c))

while queue:
    r, c, dist = queue.popleft()
    for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        nr, nc = r + dr, c + dc
        if valid(nr, nc) and (nr, nc) not in visited:
            visited.add((nr, nc))
            queue.append((nr, nc, dist + 1))

This is the same BFS skeleton used in 01 Matrix (multi-source BFS), Rotting Oranges, and Walls and Gates. The only thing that changes between problems is the starting set, the termination condition, and what you do when you visit a cell.

2. Grid neighbor generation with border detection

The pattern of computing valid neighbors and checking whether a cell is on the border:

for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
    nr, nc = r + dr, c + dc
    if 0 <= nr < rows and 0 <= nc < cols:
        is_border = nr == 0 or nr == rows - 1 or nc == 0 or nc == cols - 1

The direction array and bounds check appear in every grid problem. The border check is an additional condition specific to maze and island problems where the boundary of the grid has special meaning. You will see this same check in Surrounded Regions and Number of Closed Islands.

From understanding to recall

You have read through the BFS solution and seen how the wavefront expands level by level until it hits a border cell. The logic is clear. But can you write the direction loop, the border check, and the entrance marking from scratch in 5 minutes?

Those details matter. Forgetting to mark the entrance. Getting the bounds check wrong. Checking for the exit condition after enqueuing instead of before. These are the kinds of small mistakes that cost you time under pressure.

Spaced repetition closes that gap. You practice writing the BFS grid traversal, the direction array, and the border detection from memory at increasing intervals. After a few rounds, you do not need to think about the structure. You just write it.

Related posts

• Clone Graph - Another BFS/DFS graph traversal problem
• 01 Matrix - Multi-source BFS on a matrix
• Number of Islands - Grid traversal with connected components

CodeBricks breaks Nearest Exit from Entrance in Maze into its BFS-level-traversal and grid-border-detection building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a grid BFS problem shows up in your interview, you do not think about it. You just write it.