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

Multi-cell shortest path on an unweighted grid → breadth-first search (BFS) from the entrance — O(m·n) time, O(m·n) space.

Approach 1 — Brute force (DFS enumerate every path)

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

class Solution:
    def nearestExit(self, 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)

The insight: every step has the same cost, so the shortest path is simply the fewest edges. BFS explores the grid in concentric rings — all distance-1 cells, then all distance-2 cells — so the first exit it reaches is guaranteed to be the nearest. Mark each cell the moment you enqueue it (not when you dequeue) so it’s never queued twice.

from collections import deque

class Solution:
    def nearestExit(self, 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.