1926 · Nearest Exit from Entrance in Maze

The BFS here is the same machine as 1091 — levels are distances, mark on push. What is new is the exit predicate: a border cell is an exit unless it is the entrance. Get that wrong and every maze whose entrance sits on the border answers 0. The fix that needs no guard at all is to test the neighbour as you step onto it, after the entrance has already been sealed.

Maze (rows of . = open, + = wall)

Entrance (row, col)

Where the border is tested

Execution

idle

INVARIANT Entrance Exemption Invariant: The entrance sits on the border, but is NEVER an exit! Sealing maze[er][ec] = '+' BEFORE the BFS starts prevents an immediate 0-step false exit and guarantees O(mn) shortest path.

Press Run to begin.

0 / 0

Speed

Java · running line

popped now border cell under test in the queue an exit, by this variant entrance wall

INTERVIEW SCRIPT

How to Explain Nearest Exit in Maze to an Interviewer

1. Unweighted Grid Shortest Path = BFS

"Because all steps between adjacent cells cost 1 unit of distance, BFS guarantees we find the nearest exit in minimal steps."

2. The Entrance Exemption Trap

"The entrance often starts on the border. If we simply check 'is cell on border' on pop without checking if it's the entrance, we return 0 immediately!"

3. The Elegant Fix: Seal Entrance Upfront

"Instead of carrying a verbose !(r == er && c == ec) check on every step, simply seal maze[er][ec] = '+' upfront. Now any cell we can step onto is guaranteed not to be the entrance!"

4. Complexity Mastery

"Every cell is enqueued at most once. Total time is $O(m \cdot n)$ and auxiliary space is $O(m \cdot n)$ queue memory."

O(m·n) time, O(m·n) space · sealing the entrance before the loop starts turns the exit predicate back into a plain border test — a cell you can still step onto is by construction not the cell you started from, so there is no special case left to forget.