Nearest Exit from Entrance in Maze
Nearest Exit from Entrance in Maze: find the number of steps to the nearest exit — any empty border cell other than the entrance — or -1 if none is reachable.
- maze.length == m, maze[i].length == n
- 1 <= m, n <= 100
- maze[i][j] is either '.' or '+'.
- entrance.length == 2
- The entrance cell is empty.
Intuition
Nearest exit from entrance in maze finds the fewest steps from an entrance to any border cell that is an empty square. The word fewest on an unweighted grid points directly at BFS.
Every move costs one step, so BFS explores cells in order of increasing distance:
- The first exit BFS reaches is the nearest one, because every cell at distance d is visited before any cell at distance d + 1.
DFS would find an exit but not necessarily the closest, which is why the traversal choice matters here rather than being a preference.
An exit is an empty cell on the border — any cell in the first or last row or column. The definition has one exception that trips most solutions:
The entrance itself is not an exit, even though it sits on the border in many test cases. So the border check must be skipped for the starting cell, or the answer is 0 on inputs where it should be much larger.
Mark cells as visited when they are enqueued, not when dequeued. Marking on dequeue lets the same cell enter the queue several times before being processed, which inflates the queue and can multiply the work.
Walls are simply never enqueued. Modifying the grid in place — writing a wall character over visited cells — saves the separate visited structure when mutating the input is acceptable.
Process the queue level by level, incrementing the step count once per level. If the queue empties with no exit found, return −1.
Each cell is enqueued at most once, giving O(m × n) time and space.
Unweighted shortest path on a grid is always BFS — the tell is 'nearest', 'fewest steps', or 'minimum moves' with uniform cost. Marking cells as visited at enqueue time rather than dequeue time is the standard efficiency detail. Same shape as Rotting Oranges and Shortest Path in Binary Matrix.
Approach
Before reading on: since every step costs the same, which traversal guarantees the first exit you reach is the closest? Then state exactly what makes a cell an exit. Aim for O(m·n).
Choose BFS deliberately
Every move costs one step, so BFS visits cells in order of increasing distance and the first exit found is the nearest. DFS would find an exit but not the closest.
Define an exit precisely
An exit is an empty cell in the first or last row or column. The entrance itself does not count, even when it lies on the border — skip the check for the starting cell.
Mark visited on enqueue
Mark cells when adding them to the queue, not when removing them. Marking on dequeue lets a cell enter the queue repeatedly and multiplies the work.
Expand level by level
Process the queue one level at a time, incrementing the step count per level. Every cell in a level shares the same distance from the entrance.
Skip walls and visited cells
Never enqueue a wall or an already-seen cell. Overwriting visited cells with a wall character removes the need for a separate visited grid.
Return -1 when exhausted
If the queue empties without reaching a border cell, no exit is reachable from the entrance.
Cost of the search
Each cell is enqueued at most once with four neighbours checked, giving O(m × n) time and O(m × n) space for the queue and visited marks.
Solution & live demo
Common pitfalls
Counting the entrance as an exit
if r in (0, rows-1) or c in (0, cols-1):
return steps# only neighbours are tested, never the entrance itself
The entrance is excluded by definition. Testing the starting cell for border-ness returns 0 immediately whenever the entrance sits on the edge, which it usually does.
Using DFS
stack.pop() # depth-first
queue.popleft() # breadth-first
DFS finds an exit but not the nearest, since it commits to one corridor before trying alternatives. Only BFS guarantees the first exit reached is the closest.
Marking visited on dequeue
row, col, steps = queue.popleft() maze[row][col] = '+'
maze[r][c] = '+' queue.append((r, c, steps + 1))
Between being enqueued and dequeued, a cell can be enqueued again by another neighbour, so the queue bloats with duplicates and the work multiplies. Mark at push time.
Edge cases
It is explicitly excluded, so the search must still travel to a different border cell.
The queue drains without finding one and the answer is -1.
Found on the first expansion, giving 1 step.
No neighbours can be enqueued, so the loop ends immediately with -1.
The border test covers every cell; movement is limited to one axis.