Nearest Exit from Entrance in Maze
Problem
Given a 2D grid maze of '.' and '+' characters and an entrance coordinate, return the minimum number of steps to reach the nearest exit from the entrance, where an exit is any open cell on the maze boundary different from the entrance. Return -1 if no exit is reachable.
- maze.length == m
- maze[i].length == n
- 1 ≤ m, n ≤ 100
- maze[i][j] is either '.' or '+'
- entrance.length == 2
- 0 ≤ entrance[0] < m
- 0 ≤ entrance[1] < n
- maze[entrance[0]][entrance[1]] == '.'
Example
maze = [["+","+","+"],[".",".","."],["+","+","+"]], entrance = [1,0]2We need the nearest exit (an empty '.' cell on the boundary), but the entrance itself never counts as an exit. Start at entrance (1,0). We run BFS because every move has equal cost (1 step), so BFS explores cells in increasing distance. Layer 1 (steps = 1): - From (1,0), the only open neighbor is (1,1). Enqueue (1,1) and mark it visited. Layer 2 (steps = 2): - From (1,1), we can reach (1,2). This cell is on the boundary and is an exit. - Because BFS reaches (1,2) at the earliest possible layer, 2 is the minimum number of steps. Return 2.
Approach
Straightforward Solution
A brute-force approach might attempt all paths via DFS, but this does not guarantee the shortest path and can be inefficient due to repeated exploration.
Core Observation
The shortest path in an unweighted grid from a single source to the nearest exit is found by exploring neighbors in layers, ensuring the first exit found is the closest.
Path to Optimal
Recognizing the problem as a shortest path in an unweighted grid signals BFS as the optimal approach. BFS explores all nodes at distance d before nodes at distance d+1, ensuring the first exit found is the nearest. Marking visited cells prevents cycles and redundant work.
Optimal Approach
Use BFS starting from the entrance cell. Mark the entrance as visited in-place (set maze[sr][sc] = '+') so it is never re-enqueued and is never treated as an exit. At each BFS layer, increment the step count. For each neighbor, if it is an open cell and on the boundary (and not the entrance), return the current step count as the shortest path. Otherwise, add it to the queue and mark visited. If BFS completes without finding an exit, return -1.
Time
O(m * n)
Each cell is visited at most once. The BFS queue processes each reachable cell once, resulting in O(m*n) time for an m by n maze.
Space
O(m * n)
The queue and visited markings can hold up to O(m*n) cells in the worst case, which is necessary to track explored states and prevent revisiting.
Pattern Spotlight
BFS (Shortest Path on Unweighted Grid)
When searching for the shortest path in a grid or graph where each move has equal cost, BFS guarantees the minimal number of steps by exploring neighbors layer by layer and returning immediately upon reaching the target.
Solution
| 1 | from collections import deque
|
| 2 |
|
| 3 | class Solution:
|
| 4 | def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
|
| 5 | m, n = len(maze), len(maze[0])
|
| 6 | sr, sc = entrance
|
| 7 |
|
| 8 | q = deque([(sr, sc)])
|
| 9 | maze[sr][sc] = '+'
|
| 10 |
|
| 11 | steps = 0
|
| 12 | directions = [(1,0), (-1,0), (0,1), (0,-1)]
|
| 13 |
|
| 14 | while q:
|
| 15 | steps += 1
|
| 16 | for _ in range(len(q)):
|
| 17 | r, c = q.popleft()
|
| 18 |
|
| 19 | for dr, dc in directions:
|
| 20 | nr, nc = r + dr, c + dc
|
| 21 | if 0 <= nr < m and 0 <= nc < n and maze[nr][nc] == '.':
|
| 22 | if nr == 0 or nr == m - 1 or nc == 0 or nc == n - 1:
|
| 23 | return steps
|
| 24 | maze[nr][nc] = '+'
|
| 25 | q.append((nr, nc))
|
| 26 |
|
| 27 | return -1 |
| 1 | import java.util.LinkedList; |
| 2 | import java.util.Queue; |
| 3 | |
| 4 | class Solution { |
| 5 | public int nearestExit(char[][] maze, int[] entrance) { |
| 6 | int m = maze.length, n = maze[0].length; |
| 7 | int sr = entrance[0], sc = entrance[1]; |
| 8 | |
| 9 | Queue<int[]> q = new LinkedList<>(); |
| 10 | q.offer(new int[]{sr, sc}); |
| 11 | maze[sr][sc] = '+'; // mark entrance as visited |
| 12 | |
| 13 | int steps = 0; |
| 14 | int[][] directions = {{1,0}, {-1,0}, {0,1}, {0,-1}}; |
| 15 | |
| 16 | while (!q.isEmpty()) { |
| 17 | steps++; |
| 18 | int size = q.size(); |
| 19 | for (int i = 0; i < size; i++) { |
| 20 | int[] curr = q.poll(); |
| 21 | int r = curr[0], c = curr[1]; |
| 22 | |
| 23 | for (int[] d : directions) { |
| 24 | int nr = r + d[0], nc = c + d[1]; |
| 25 | if (nr >= 0 && nr < m && nc >= 0 && nc < n && maze[nr][nc] == '.') { |
| 26 | if (nr == 0 || nr == m - 1 || nc == 0 || nc == n - 1) { |
| 27 | return steps; |
| 28 | } |
| 29 | maze[nr][nc] = '+'; |
| 30 | q.offer(new int[]{nr, nc}); |
| 31 | } |
| 32 | } |
| 33 | } |
| 34 | } |
| 35 | |
| 36 | return -1; |
| 37 | } |
| 38 | } |
| 1 | #include <vector> |
| 2 | #include <queue> |
| 3 | |
| 4 | using namespace std; |
| 5 | |
| 6 | class Solution { |
| 7 | public: |
| 8 | int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) { |
| 9 | int m = maze.size(), n = maze[0].size(); |
| 10 | int sr = entrance[0], sc = entrance[1]; |
| 11 | |
| 12 | queue<pair<int,int>> q; |
| 13 | q.emplace(sr, sc); |
| 14 | maze[sr][sc] = '+'; // mark entrance as visited |
| 15 | |
| 16 | int steps = 0; |
| 17 | vector<pair<int,int>> directions = {{1,0}, {-1,0}, {0,1}, {0,-1}}; |
| 18 | |
| 19 | while (!q.empty()) { |
| 20 | steps++; |
| 21 | int size = q.size(); |
| 22 | for (int i = 0; i < size; i++) { |
| 23 | auto [r, c] = q.front(); |
| 24 | q.pop(); |
| 25 | |
| 26 | for (auto& d : directions) { |
| 27 | int nr = r + d.first, nc = c + d.second; |
| 28 | if (nr >= 0 && nr < m && nc >= 0 && nc < n && maze[nr][nc] == '.') { |
| 29 | if (nr == 0 || nr == m - 1 || nc == 0 || nc == n - 1) { |
| 30 | return steps; |
| 31 | } |
| 32 | maze[nr][nc] = '+'; |
| 33 | q.emplace(nr, nc); |
| 34 | } |
| 35 | } |
| 36 | } |
| 37 | } |
| 38 | |
| 39 | return -1; |
| 40 | } |
| 41 | }; |
| 1 | var nearestExit = function(maze, entrance) { |
| 2 | const m = maze.length, n = maze[0].length; |
| 3 | const [sr, sc] = entrance; |
| 4 | |
| 5 | const q = [[sr, sc]]; |
| 6 | let front = 0; |
| 7 | maze[sr][sc] = '+'; // mark entrance as visited |
| 8 | |
| 9 | let steps = 0; |
| 10 | const directions = [[1,0], [-1,0], [0,1], [0,-1]]; |
| 11 | |
| 12 | while (front < q.length) { |
| 13 | steps++; |
| 14 | const size = q.length - front; |
| 15 | for (let i = 0; i < size; i++) { |
| 16 | const [r, c] = q[front++]; |
| 17 | |
| 18 | for (const [dr, dc] of directions) { |
| 19 | const nr = r + dr, nc = c + dc; |
| 20 | if (nr >= 0 && nr < m && nc >= 0 && nc < n && maze[nr][nc] === '.') { |
| 21 | if (nr === 0 || nr === m - 1 || nc === 0 || nc === n - 1) { |
| 22 | return steps; |
| 23 | } |
| 24 | maze[nr][nc] = '+'; |
| 25 | q.push([nr, nc]); |
| 26 | } |
| 27 | } |
| 28 | } |
| 29 | } |
| 30 | |
| 31 | return -1; |
| 32 | }; |
Step-by-Step Solution
Initialize BFS Queue and Mark Entrance as Visited
| 5 | m, n = len(maze), len(maze[0])
|
| 6 | sr, sc = entrance
|
| 8 | q = deque([(sr, sc)])
|
| 9 | maze[sr][sc] = '+'
|
Objective
To set up the BFS starting point with the entrance cell and mark it as visited to avoid revisiting.
Key Insight
Marking the entrance as visited in-place (setting it to '+') prevents revisiting the start and guarantees the entrance is not counted as an exit even if it lies on the boundary. Initializing the queue with the entrance coordinates sets the stage for layer-by-layer exploration. This ensures the BFS only explores valid paths and does not revisit cells, maintaining correctness and efficiency.
Interview Quick-Check
Core Logic
Marking the entrance as visited before BFS begins prevents cycles and ensures the entrance is not considered an exit.
State & Boundaries
Initialize the queue with the entrance coordinates to start BFS from the correct source.
Common Pitfalls & Bugs
Failing to mark the entrance as visited can cause infinite loops or incorrect exit detection.
Perform BFS Layer-by-Layer to Find Nearest Exit
| 11 | steps = 0
|
| 12 | directions = [(1,0), (-1,0), (0,1), (0,-1)]
|
| 14 | while q:
|
| 15 | steps += 1
|
| 16 | for _ in range(len(q)):
|
| 17 | r, c = q.popleft()
|
| 19 | for dr, dc in directions:
|
| 20 | nr, nc = r + dr, c + dc
|
| 21 | if 0 <= nr < m and 0 <= nc < n and maze[nr][nc] == '.':
|
| 22 | if nr == 0 or nr == m - 1 or nc == 0 or nc == n - 1:
|
| 23 | return steps
|
| 24 | maze[nr][nc] = '+'
|
| 25 | q.append((nr, nc))
|
Objective
To explore the maze in increasing order of distance from the entrance, checking neighbors and returning the step count upon reaching an exit.
Key Insight
BFS processes all nodes at the current distance before moving to the next, ensuring the first exit found is the shortest path. Checking if a neighbor is on the boundary and open identifies exits. Marking neighbors as visited when enqueued prevents revisiting and redundant work. Incrementing steps at each BFS layer tracks the distance from the entrance.
Interview Quick-Check
Core Logic
Increment steps at each BFS layer and check neighbors for exits to guarantee the shortest path is found.
State & Boundaries
Only enqueue neighbors that are within bounds, open, and unvisited to maintain BFS correctness.
Common Pitfalls & Bugs
Returning when an exit cell is dequeued can produce the wrong step count when steps is incremented per BFS layer. Returning as soon as the exit is discovered keeps steps equal to the number of moves taken.
Complexity
Each cell is enqueued and dequeued at most once, ensuring O(m*n) time complexity.
Return -1 if No Exit is Reachable
| 27 | return -1 |
Objective
To signal that no path to an exit exists after BFS exhausts all reachable cells.
Key Insight
If BFS completes without finding any exit, it means the entrance is enclosed or no boundary cell is reachable. Returning -1 correctly communicates the impossibility of escape.
Interview Quick-Check
Core Logic
Returning -1 after BFS completes ensures the function correctly handles mazes with no reachable exits.
Line Analysis
This solution has 5 Critical lines interviewers watch for.
return stepsReturn the current step count as the shortest path length to the exit.
Returning immediately upon finding an exit leverages BFS's guarantee that this is the minimal number of steps required.
maze[sr][sc] = '+'Mark the entrance cell as visited by setting it to '+'.
Marking the entrance as visited prevents revisiting it during BFS, avoiding infinite loops and incorrect exit detection.
if 0 <= nr < m and 0 <= nc < n and maze[nr][nc] == '.':Check if the neighbor is within maze bounds and is an open cell ('.').
Validating neighbors prevents out-of-bounds errors and ensures BFS only explores traversable cells.
if nr == 0 or nr == m - 1 or nc == 0 or nc == n - 1:Check if the neighbor cell is on the maze boundary, indicating an exit.
Identifying boundary cells allows immediate detection of exits, enabling BFS to return the shortest path length promptly.
maze[nr][nc] = '+'Mark the neighbor cell as visited by setting it to '+'.
Marking visited cells upon enqueueing prevents revisiting and infinite loops, maintaining BFS efficiency and correctness.
q = deque([(sr, sc)])Initialize the BFS queue with the entrance cell coordinates.
Starting BFS from the entrance ensures exploration begins at the correct source, enabling shortest path discovery.
steps += 1Increment the step count at the start of each BFS layer.
Incrementing steps here correctly counts the distance from the entrance to the current layer of cells being explored.
r, c = q.popleft()Dequeue the next cell coordinates from the BFS queue.
Dequeuing in FIFO order maintains BFS's layer-by-layer traversal property, critical for shortest path correctness.
q.append((nr, nc))Enqueue the neighbor cell coordinates for future BFS exploration.
Adding neighbors to the queue schedules them for exploration in subsequent BFS layers, enabling systematic traversal.
while q:Start the BFS loop, continuing while the queue is not empty.
The loop processes cells layer by layer, exploring all reachable positions until no more remain or an exit is found.
for _ in range(len(q)):Iterate over all cells in the current BFS layer.
Processing all nodes at the current distance before moving deeper ensures BFS explores in order of increasing distance.
return -1Return -1 if BFS completes without finding any exit.
Returning -1 signals that no path to an exit exists, correctly handling enclosed or blocked mazes.
directions = [(1,0), (-1,0), (0,1), (0,-1)]Define the four possible movement directions (up, down, left, right).
Enumerating directions simplifies neighbor exploration and ensures all valid moves are considered.
for dr, dc in directions:Iterate over all four possible movement directions.
Exploring all neighbors ensures BFS considers every reachable adjacent cell for potential paths.
steps = 0Initialize the step counter to zero.
Tracking the number of steps taken from the entrance is essential for returning the shortest path length.
nr, nc = r + dr, c + dcCalculate the neighbor cell coordinates by adding direction offsets.
Computing neighbor positions is necessary to check their validity and enqueue them if appropriate.
m, n = len(maze), len(maze[0])Store the maze dimensions m (rows) and n (columns).
Caching the maze size simplifies boundary checks and improves code readability by avoiding repeated len() calls.
sr, sc = entranceUnpack the entrance coordinates into sr and sc.
Extracting the starting row and column clarifies the BFS starting point and improves code clarity.
Test Your Understanding
Why does BFS guarantee that the first exit found is the nearest exit in terms of steps?
Because BFS explores all nodes at distance d before any nodes at distance d+1, the first exit discovered during BFS is guaranteed to be the closest in terms of the number of steps from the entrance.
Related Problems
BFS pattern
Don't just read it. Drill it.
Reconstruct Nearest Exit from Entrance in Maze from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Nearest Exit from Entrance in Maze drill