1926. Nearest Exit from Entrance in Maze

Description

The problem involves navigating through a maze to find the nearest exit. Given a maze represented as a grid of cells, with some cells containing walls ('+') and others being empty ('.'), the task is to find the shortest path from a given entrance to the nearest exit. An exit is defined as an empty cell on the boundary of the maze that is not the entrance.

Intuition

The most efficient way to find the shortest path in an unweighted grid is by using a Breadth-First Search (BFS). BFS explores all possible moves level by level, ensuring that the first time it reaches an exit, that path is the shortest one. By pushing all possible exits into a queue initially and then performing BFS, we can efficiently determine the shortest path from the entrance to the nearest exit.

Approach

1. Identify Exits: Iterate through the maze and identify all potential exits (cells on the boundary of the maze that are not walls or the entrance). Push these into a queue with an initial distance of 0.
2. Breadth-First Search: Use BFS to explore all possible paths from the entrance. From each cell, move in all four possible directions (up, down, left, right) and track the distance from the entrance.
3. Tracking Visits: Use a visited map to keep track of cells that have already been checked to avoid reprocessing.
4. Return the Result: As soon as the BFS reaches the entrance, return the distance as it represents the shortest path to an exit. If no path is found, return -1.

Complexity

Time Complexity:

(O(n \times m)), where (n) is the number of rows and (m) is the number of columns in the maze. This is because in the worst case, we might need to check every cell in the maze.

Space Complexity:

(O(n \times m)), due to the storage required for the queue and the visited map used during the BFS traversal.

Code

C++

class Solution {
public:
    int nearestExit(vector>& maze, vector& entrance) {
        vector> st;
        int rows = maze.size();
        int cols = maze[0].size();

        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (maze[i][j] == '.' && (i == 0 || i == rows - 1 || j == 0 || j == cols - 1) && !isEquals(vector{i, j}, entrance)) {
                    st.push_back({i, j, 0});
                }
            }
        }
        return bfs(st, maze, entrance);
    }

private:
    bool isEquals(const vector& a, const vector& b) {
        return a[0] == b[0] && a[1] == b[1];
    }

    int bfs(vector>& st, vector>& maze, vector& start) {
        vector> directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        unordered_map> visited;

        while (!st.empty()) {
            auto [row, col, len] = st.front();
            st.erase(st.begin());
            visited[row][col] = true;

            for (auto& dir : directions) {
                int r = row + dir[0];
                int c = col + dir[1];

                if (isEquals(vector{r, c}, start)) return len + 1;
                if (r < 0 || c < 0 || r >= maze.size() || c >= maze[0].size() || maze[r][c] == '+' || visited[r][c]) continue;

                st.push_back({r, c, len + 1});
                visited[r][c] = true;
            }
        }
        return -1;
    }
};

Python

class Solution:
    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
        st = []
        rows, cols = len(maze), len(maze[0])

        for i in range(rows):
            for j in range(cols):
                if maze[i][j] == "." and (i == 0 or i == rows - 1 or j == 0 or j == cols - 1) and [i, j] != entrance:
                    st.append((i, j, 0))

        return self.bfs(st, maze, entrance)

    def isEquals(self, a: List[int], b: List[int]) -> bool:
        return a[0] == b[0] and a[1] == b[1]

    def bfs(self, st: List[tuple], maze: List[List[str]], start: List[int]) -> int:
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        visited = set()

        while st:
            row, col, length = st.pop(0)
            visited.add((row, col))

            for r_offset, c_offset in directions:
                r, c = row + r_offset, col + c_offset

                if [r, c] == start:
                    return length + 1
                if r < 0 or c < 0 or r >= len(maze) or c >= len(maze[0]) or maze[r][c] == "+" or (r, c) in visited:
                    continue

                st.append((r, c, length + 1))
                visited.add((r, c))

        return -1

Java

class Solution {
    public int nearestExit(char[][] maze, int[] entrance) {
        List st = new ArrayList<>();
        int rows = maze.length;
        int cols = maze[0].length;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (maze[i][j] == '.' && (i == 0 || i == rows - 1 || j == 0 || j == cols - 1) && !isEquals(new int[]{i, j}, entrance)) {
                    st.add(new int[]{i, j, 0});
                }
            }
        }
        return bfs(st, maze, entrance);
    }

    private boolean isEquals(int[] a, int[] b) {
        return a[0] == b[0] && a[1] == b[1];
    }

    private int bfs(List st, char[][] maze, int[] start) {
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        Set visited = new HashSet<>();

        while (!st.isEmpty()) {
            int[] cur = st.remove(0);
            int row = cur[0], col = cur[1], len = cur[2];
            visited.add(row + "," + col);

            for (int[] dir : directions) {
                int r = row + dir[0];
                int c = col + dir[1];

                if (isEquals(new int[]{r, c}, start)) return len + 1;
                if (r < 0 || c < 0 || r >= maze.length || c >= maze[0].length || maze[r][c] == '+' || visited.contains(r + "," + c)) continue;

                st.add(new int[]{r, c, len + 1});
                visited.add(r + "," + c);
            }
        }
        return -1;
    }
}

JavaScript

var nearestExit = function (maze, entrance) {
    let st = []
    for (let i = 0; i < maze.length; i++) {
        for (let j = 0; j < maze[0].length; j++) {
            if (maze[i][j] == "." && (i == 0 || i == maze.length - 1 || j == 0 || j == maze[0].length - 1) && !isEquals([i, j], entrance)) {
                st.push([i, j, 0])
            }
        }
    }
    return bfs(st, maze, entrance)
};
function isEquals(a, b) {
    return a[0] == b[0] && a[1] == b[1]
}
function bfs(st, maze, start) {
    let directions = [[0, 1], [0, -1], [1, 0], [-1, 0]], visited = {}
    while (st.length) {
        const [row, col, len] = st.shift()
        visited[[row, col]] = 1
        for (let i of directions) {
            let r = row + i[0], c = col + i[1]
            if (isEquals([r, c], start)) return len + 1
            if (r < 0 || c < 0 || r > maze.length - 1 || c > maze[0].length - 1 || maze[r][c] == "+" || visited[[r, c]]) continue
            st.push([r, c, len + 1])
            visited[[r, c]] = 1
        }
    }
    return -1
}