Nearest Exit from Entrance in Maze
Problem
You're given a grid of . (open) and # (wall) cells and an entrance position. Return the fewest steps to reach any open cell on the grid border that isn't the entrance, or -1 if impossible. Standard BFS from the entrance.
maze (rows separated by ';') = ".#.;..#;.##", entrance = (0,0)1from collections import deque
def nearest_exit(maze, entry):
m, n = len(maze), len(maze[0])
q = deque([(entry[0], entry[1], 0)])
seen = {entry}
dirs = [(1,0),(-1,0),(0,1),(0,-1)]
while q:
r, c, d = q.popleft()
if d > 0 and (r in (0, m - 1) or c in (0, n - 1)): return d
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and maze[nr][nc] != '#' and (nr, nc) not in seen:
seen.add((nr, nc)); q.append((nr, nc, d + 1))
return -1function nearestExit(maze, entry) {
const m = maze.length, n = maze[0].length;
const q = [[entry[0], entry[1], 0]];
const seen = new Set([entry[0] + "," + entry[1]]);
const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
while (q.length) {
const [r, c, d] = q.shift();
const onBorder = r === 0 || c === 0 || r === m - 1 || c === n - 1;
if (d > 0 && onBorder) return d;
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc, key = nr + "," + nc;
if (nr<0||nc<0||nr>=m||nc>=n||maze[nr][nc] === '#'||seen.has(key)) continue;
seen.add(key); q.push([nr, nc, d + 1]);
}
}
return -1;
}class Solution {
public int nearestExit(char[][] maze, int[] entry) {
int m = maze.length, n = maze[0].length;
Deque<int[]> q = new ArrayDeque<>();
q.offer(new int[]{ entry[0], entry[1], 0 });
boolean[][] seen = new boolean[m][n];
seen[entry[0]][entry[1]] = true;
int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
while (!q.isEmpty()) {
int[] f = q.poll();
int r = f[0], c = f[1], d = f[2];
boolean onBorder = r == 0 || c == 0 || r == m - 1 || c == n - 1;
if (d > 0 && onBorder) return d;
for (int[] dd : dirs) {
int nr = r + dd[0], nc = c + dd[1];
if (nr<0||nc<0||nr>=m||nc>=n||maze[nr][nc]=='#'||seen[nr][nc]) continue;
seen[nr][nc] = true; q.offer(new int[]{ nr, nc, d + 1 });
}
}
return -1;
}
}int nearestExit(vector<string>& maze, vector<int>& entry) {
int m = maze.size(), n = maze[0].size();
queue<tuple<int,int,int>> q;
q.push({entry[0], entry[1], 0});
vector<vector<bool>> seen(m, vector<bool>(n, false));
seen[entry[0]][entry[1]] = true;
int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
while (!q.empty()) {
auto [r, c, d] = q.front(); q.pop();
bool onBorder = r == 0 || c == 0 || r == m - 1 || c == n - 1;
if (d > 0 && onBorder) return d;
for (auto& dd : dirs) {
int nr = r + dd[0], nc = c + dd[1];
if (nr<0||nc<0||nr>=m||nc>=n||maze[nr][nc]=='#'||seen[nr][nc]) continue;
seen[nr][nc] = true; q.push({nr, nc, d + 1});
}
}
return -1;
}Explanation
Because every step in the maze costs the same, the closest exit is found by BFS — we expand outward from the entrance one ring at a time, so the first border cell we reach is guaranteed to be the nearest.
The queue holds cells as (r, c, d) where d is the number of steps from the entrance. A seen set keeps us from walking back over visited cells. From each cell we try the four neighbors in dirs, skipping anything off the grid, any wall '#', or anything already seen.
An exit is an open cell on the border that isn't the entrance itself. We check this with d > 0 and (r in (0, m-1) or c in (0, n-1)) — the d > 0 guard is important so the entrance (which may itself be on the border) doesn't count as its own exit.
Example: maze .#. / ..# / .## with entrance (0,0). BFS steps to (1,0) at distance 1, which lies on the left border and is open, so the answer is 1.
If the queue drains without ever popping a valid border cell, no exit is reachable and we return -1.