Nearest Exit From a Maze Entrance

medium graph bfs grid

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.

Inputmaze (rows separated by ';') = ".#.;..#;.##", entrance = (0,0)

Output2

BFS finds the closest border open cell that is not the entry.

maze (rows by ';', use . and #)

entry row

entry col

from 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 -1

function 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;
}

Time: O(m·n) Space: O(m·n)