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
Every move costs the same, so the shortest route is found by breadth-first search: expand the frontier one ring at a time and the first exit you touch is the nearest. Depth-first would find an exit but not necessarily the closest.
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).
Why BFS and not DFS
All moves cost 1, which makes this an unweighted shortest-path problem. BFS explores in order of distance, so every cell is first reached by the shortest possible route and the first exit encountered is the nearest — you can return immediately. DFS plunges down one corridor to the end and would have to explore the entire maze and compare, doing far more work for the same answer.
Tracking distance in the queue
Push (row, col, steps) and increment steps when enqueueing neighbours. The alternative is a level-by-level loop that drains the queue in batches and counts rounds — both are correct, and carrying the count per cell is slightly simpler here since it needs no batch bookkeeping. Mark cells as walls ('+') the moment they are enqueued, not when they are dequeued, so the same cell is never queued twice.
Defining an exit precisely
An exit is an empty cell on the border that is not the entrance. Two checks are needed: the cell lies in row 0, the last row, column 0, or the last column; and it differs from the entrance coordinates. Forgetting the second condition makes the entrance itself count as an exit and returns 0 for every input. Note the entrance is never an exit even though it is often on the border. Cost is O(m·n) — each cell is enqueued at most once.
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.