Nearest Exit from Entrance in Maze

Problem

You’re given an m x n grid maze. Each cell is either . (empty, walkable) or + (a wall). You also get entrance = [r, c], the coordinates of an empty cell where you start.

In one step you may move up, down, left, or right into an adjacent empty cell (you cannot step into walls or off the grid). An exit is any empty cell on the border of the maze — the first or last row, or the first or last column — other than the entrance itself.

Return the number of steps in the shortest path from the entrance to the nearest exit, or -1 if no exit is reachable.

Examples

• maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2] → 1 — step up to (0,2), an empty border cell.
• maze = [["+","+","+"],[".",".","."],["+","+","+"]], entrance = [1,0] → 2 — the entrance sits on the border but doesn’t count; walk right to (1,1) then (1,2), which is a border exit.
• maze = [[".","+"]], entrance = [0,0] → -1 — the only other cell is a wall, so no exit is reachable.

Constraints

• 1 <= m, n <= 100
• Every cell is . or +; the entrance is always an empty cell.
• All edges have equal cost (each step = 1), which is what makes plain BFS optimal.

Think about it first

TL;DR

Shortest path on an unweighted grid: run breadth-first search (BFS) from the entrance. O(m·n) time, O(m·n) space.

Approach 1 — Brute force (DFS enumerate every path)

Recursively walk every path from the entrance, and whenever you reach a border exit, record the path length; return the minimum. Depth-first search (DFS) explores one path to its end before backtracking.

def nearestExit(maze: list[list[str]], entrance: list[int]) -> int:
    m, n = len(maze), len(maze[0])
    er, ec = entrance
    best = float("inf")

    def is_exit(r: int, c: int) -> bool:
        on_border = r == 0 or r == m - 1 or c == 0 or c == n - 1
        return on_border and not (r == er and c == ec)

    def dfs(r: int, c: int, steps: int) -> None:
        nonlocal best
        if is_exit(r, c):
            best = min(best, steps)
            return
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n and maze[nr][nc] == ".":
                maze[nr][nc] = "+"          # mark to avoid cycles
                dfs(nr, nc, steps + 1)
                maze[nr][nc] = "."          # backtrack

    maze[er][ec] = "+"
    dfs(er, ec, 0)
    return -1 if best == float("inf") else best

Complexity: because it backtracks (un-marks cells), a single cell can be visited on exponentially many distinct paths — O(4^(m·n)) in the worst case. With a 100×100 grid this never finishes.

Approach 2 — BFS from the entrance (optimal)

Every step has the same cost, so the shortest path is the one with the fewest edges. BFS explores the grid in concentric rings: all distance-1 cells, then all distance-2 cells, and so on. The first exit it reaches is therefore the nearest. Mark each cell the moment you enqueue it (not when you dequeue) so it is never queued twice.

flowchart TD
    A[Pop cell and its step count] --> B[For each of 4 neighbors]
    B --> C{In bounds and empty?}
    C -->|No| B
    C -->|Yes| D{On the border?}
    D -->|Yes| E[Return steps + 1]
    D -->|No| F[Mark visited, enqueue with steps + 1]
    F --> B

from collections import deque

def nearestExit(maze: list[list[str]], entrance: list[int]) -> int:
    m, n = len(maze), len(maze[0])
    er, ec = entrance
    maze[er][ec] = "+"                       # block the start so it can't be an "exit"
    queue = deque([(er, ec, 0)])             # (row, col, steps)

    while queue:
        r, c, steps = queue.popleft()
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n and maze[nr][nc] == ".":
                if nr == 0 or nr == m - 1 or nc == 0 or nc == n - 1:
                    return steps + 1         # first border cell reached = nearest exit
                maze[nr][nc] = "+"           # visited
                queue.append((nr, nc, steps + 1))
    return -1

Walkthrough (maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2]): block (1,2). Dequeue (1,2,0). Neighbor up is (0,2), empty and on the top border → return 0 + 1 = 1. Nearest exit found in one step.

Complexity: each cell is enqueued and dequeued at most once and we scan its 4 neighbors → O(m·n) time, O(m·n) space for the queue and visited marks.

Common pitfalls

• Counting the entrance as an exit. It’s on the border but explicitly excluded — block it before the search so the code can’t return it.
• Marking visited on dequeue instead of enqueue. That lets the same cell be queued multiple times, inflating the queue and (with per-level distance) risking wrong counts.
• Checking the border on the popped cell rather than the neighbor. You want to return the moment you reach an exit; testing after enqueueing wastes a level.
• Reaching for DFS or Dijkstra. DFS finds a path, not the shortest; Dijkstra is overkill because all weights are equal — BFS is the right tool for unweighted shortest paths.

Pattern takeaway

On an unweighted grid or graph, “shortest number of moves” means BFS — it settles nodes in nondecreasing distance order, so the first time you touch a target that distance is optimal. Prefer BFS over DFS whenever the question asks for a shortest/minimum path; prefer DFS when you only need reachability, connectivity, or to enumerate/backtrack. Mark cells visited at enqueue time to keep the work linear.