Problem Description

You are given a 2D maze represented by a grid of characters, where each cell is either a '.' (an empty space you can walk through) or a '+' (a wall you cannot pass through). You are also given an entrance represented as a pair of coordinates [entrance_row, entrance_col] indicating your starting position in the maze (which is always an empty cell).

Your goal is to find the minimum number of steps required to reach the nearest exit from the entrance. An exit is any empty cell located on the border of the maze, except for the entrance itself. You can move up, down, left, or right, but cannot move through walls or outside the maze.

Constraints:

• There may be zero or more exits.
• You cannot reuse cells you've already visited in the same path.
• Return -1 if there is no possible exit.

Thought Process

The problem is essentially a shortest-path search in a grid, starting from a given cell and seeking the closest border cell (except the entrance itself). At first glance, you might consider trying all possible paths recursively (brute-force), but this quickly becomes inefficient as the grid size grows.

To optimize, we notice that we want the minimum number of steps to an exit. This is a classic scenario for Breadth-First Search (BFS) because BFS explores all positions at distance d before moving to distance d+1, guaranteeing the first exit found is the nearest.

We also need to make sure we don't revisit cells, to prevent cycles and redundant work. By marking cells as visited as soon as they are added to the BFS queue, we avoid exploring the same location multiple times.

Solution Approach

Here’s how we can solve the problem step-by-step:

1. Initialize BFS: Start a queue with the entrance cell and a step count of 0. Mark the entrance as visited.
2. Explore Directions: For each cell dequeued, check its four neighbors (up, down, left, right).
3. Check Validity: For each neighbor, ensure it is within bounds, not a wall, and not already visited.
4. Check for Exit: If a valid neighbor is on the border (first or last row/column) and is not the entrance, return the current step count + 1 as the answer.
5. Continue BFS: Otherwise, add the neighbor to the queue and mark it as visited.
6. No Exit: If the queue is exhausted without finding an exit, return -1.

Design choices explained:

• We use BFS because it guarantees finding the shortest path in an unweighted grid.
• We use a queue for BFS and a visited set (or marking the grid) for O(1) lookups to avoid revisiting cells.
• We check for exits only when popping from the queue, ensuring the minimum steps.

Example Walkthrough

Sample Input:

maze = [
  ['+','+','.','+'],
  ['.','.','.','+'],
  ['+','+','+','.']
]
entrance = [1,2]
    

1. Start at (1,2), step count = 0.
2. From (1,2), possible moves: (0,2), (2,2), (1,1), (1,3).
3. (0,2) is an empty cell on the border and not the entrance. We've found the nearest exit in 1 step!

The BFS ensures we find (0,2) first, before any farther exits, so the answer is 1.

Time and Space Complexity

Brute-force approach:

• Would involve exploring all possible paths, with exponential time in the worst case: O(4^(m*n)), where m and n are maze dimensions.
• Space would also be exponential due to recursion stack and path storage.

• Each cell is visited at most once. Total time is O(m*n).
• Space is O(m*n) for the queue and visited set.
• Efficient for large mazes, as it avoids redundant work.

Summary

We solved the "Nearest Exit from Entrance in Maze" problem by recognizing it as a shortest-path search and applying Breadth-First Search for efficiency. BFS ensures we find the nearest exit first, and by marking visited cells, we avoid cycles and unnecessary work. The approach is both elegant and optimal for this type of grid-based pathfinding problem.

Code Implementation

from collections import deque

class Solution:
    def nearestExit(self, maze, entrance):
        m, n = len(maze), len(maze[0])
        q = deque()
        q.append((entrance[0], entrance[1], 0))
        maze[entrance[0]][entrance[1]] = '+'
        
        dirs = [(-1,0), (1,0), (0,-1), (0,1)]
        
        while q:
            x, y, steps = q.popleft()
            for dx, dy in dirs:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n and maze[nx][ny] == '.':
                    if nx == 0 or nx == m-1 or ny == 0 or ny == n-1:
                        return steps + 1
                    maze[nx][ny] = '+'
                    q.append((nx, ny, steps + 1))
        return -1
      

#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        int m = maze.size(), n = maze[0].size();
        queue<tuple<int, int, int>> q;
        q.emplace(entrance[0], entrance[1], 0);
        maze[entrance[0]][entrance[1]] = '+';
        int dirs[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
        
        while (!q.empty()) {
            auto [x, y, steps] = q.front(); q.pop();
            for (auto& d : dirs) {
                int nx = x + d[0], ny = y + d[1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && maze[nx][ny] == '.') {
                    if (nx == 0 || nx == m-1 || ny == 0 || ny == n-1)
                        return steps + 1;
                    maze[nx][ny] = '+';
                    q.emplace(nx, ny, steps + 1);
                }
            }
        }
        return -1;
    }
};
      

import java.util.*;

class Solution {
    public int nearestExit(char[][] maze, int[] entrance) {
        int m = maze.length, n = maze[0].length;
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{entrance[0], entrance[1], 0});
        maze[entrance[0]][entrance[1]] = '+';
        int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
        
        while (!q.isEmpty()) {
            int[] curr = q.poll();
            int x = curr[0], y = curr[1], steps = curr[2];
            for (int[] d : dirs) {
                int nx = x + d[0], ny = y + d[1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && maze[nx][ny] == '.') {
                    if (nx == 0 || nx == m-1 || ny == 0 || ny == n-1)
                        return steps + 1;
                    maze[nx][ny] = '+';
                    q.offer(new int[]{nx, ny, steps + 1});
                }
            }
        }
        return -1;
    }
}
      

/**
 * @param {character[][]} maze
 * @param {number[]} entrance
 * @return {number}
 */
var nearestExit = function(maze, entrance) {
    const m = maze.length, n = maze[0].length;
    const q = [];
    q.push([entrance[0], entrance[1], 0]);
    maze[entrance[0]][entrance[1]] = '+';
    const dirs = [[-1,0],[1,0],[0,-1],[0,1]];
    
    while (q.length) {
        const [x, y, steps] = q.shift();
        for (const [dx, dy] of dirs) {
            const nx = x + dx, ny = y + dy;
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && maze[nx][ny] === '.') {
                if (nx === 0 || nx === m-1 || ny === 0 || ny === n-1)
                    return steps + 1;
                maze[nx][ny] = '+';
                q.push([nx, ny, steps + 1]);
            }
        }
    }
    return -1;
};