You are given an m x n matrix maze (0-indexed) with empty cells (represented as '.') and walls (represented as '+'). You are also given the entrance of the maze, where entrance = [entrancerow, entrancecol] denotes the row and column of the cell you are initially standing at.
In one step, you can move one cell up, down, left, or right. You cannot step into a cell with a wall, and you cannot step outside the maze. Your goal is to find the nearest exit from the entrance. An exit is defined as an empty cell that is at the border of the maze. The entrance does not count as an exit.
Return the number of steps in the shortest path from the entrance to the nearest exit, or -1 if no such path exists.
Example 1:
Input: maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2] Output: 1 Explanation: There are 3 exits in this maze at [1,0], [0,2], and [2,3]. Initially, you are at the entrance cell [1,2]. - You can reach [1,0] by moving 2 steps left. - You can reach [0,2] by moving 1 step up. It is impossible to reach [2,3] from the entrance. Thus, the nearest exit is [0,2], which is 1 step away.
Example 2:
Input: maze = [["+","+","+"],[".",".","."],["+","+","+"]], entrance = [1,0] Output: 2 Explanation: There is 1 exit in this maze at [1,2]. [1,0] does not count as an exit since it is the entrance cell. Initially, you are at the entrance cell [1,0]. - You can reach [1,2] by moving 2 steps right. Thus, the nearest exit is [1,2], which is 2 steps away.
Example 3:
Input: maze = [[".","+"]], entrance = [0,0] Output: -1 Explanation: There are no exits in this maze.
Constraints:
maze.length == mmaze[i].length == n1 <= m, n <= 100maze[i][j] is either '.' or '+'.entrance.length == 20 <= entrancerow < m0 <= entrancecol < nentrance will always be an empty cell.Problem Overview: You are given a 2D maze with walls ('+') and empty cells ('.'). Starting from an entrance cell, you must find the minimum number of steps required to reach the nearest exit. An exit is any empty cell on the maze boundary except the entrance itself.
Approach 1: Breadth-First Search (BFS) (Time: O(m*n), Space: O(m*n))
This problem reduces to finding the shortest path in an unweighted grid. Breadth-First Search works perfectly because it explores cells level by level. Start from the entrance, push it into a queue, and expand in four directions (up, down, left, right). Mark visited cells to avoid revisiting. The first time BFS reaches a boundary cell that is not the entrance, you have found the nearest exit. Each cell is processed at most once, so the total work is proportional to the number of cells in the grid.
The key insight: BFS guarantees the shortest path in an unweighted graph. A maze grid is simply a graph where each open cell connects to its neighbors. As soon as you pop a boundary cell from the queue, its distance from the entrance is the minimum number of steps required.
Approach 2: Depth-First Search (DFS) (Time: O(m*n), Space: O(m*n))
A Depth-First Search approach explores all possible paths recursively while tracking the current distance from the entrance. Each recursive call moves to one of the four directions if the cell is within bounds, not a wall, and not visited. When DFS reaches a boundary cell that is not the entrance, update the minimum steps found so far.
DFS works but is less efficient for shortest-path problems in grids because it explores deep paths before discovering shorter ones. You must track visited cells and backtrack correctly. In dense mazes this leads to unnecessary exploration compared to BFS.
The maze itself is a classic matrix traversal problem where each cell can be treated as a node in a graph.
Recommended for interviews: The BFS solution is the expected answer. Interviewers want to see that you recognize the problem as a shortest-path search in an unweighted grid. DFS demonstrates basic traversal knowledge, but BFS shows stronger algorithmic judgment because it naturally guarantees the minimum number of steps.
In this approach, we use the Breadth-First Search (BFS) algorithm to explore the maze. BFS is suitable because it explores nodes layer by layer, ensuring that the shortest path is found. We initialize a queue with the entrance cell and explore its neighbors (up, down, left, right). If a neighbor is an unvisited empty cell and is on the boundary (except the entrance), it can be considered as an exit.
Each time we explore a cell, we mark it as visited by changing its state to '+'. This prevents revisiting nodes, which ensures that we won't traverse the same path multiple times. We keep track of steps taken from the entrance to the current cell, and if we reach an exit, we return the number of steps. If the queue is exhausted without finding an exit, we return -1.
This implementation uses a queue to facilitate the BFS. It starts by enqueuing the entrance and marking it as visited by changing it to '+'. Four possible movement directions are considered (right, down, left, up). As each cell is processed, its unvisited neighbors are enqueued. If a neighbor is a border cell but not the entrance, it is considered the closest exit, and the steps taken are returned.
Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the maze. In the worst case, all cells are traversed.
Space Complexity: O(m * n) for the queue used in BFS.
In this approach, we use the Depth-First Search (DFS) algorithm to explore the maze. DFS might not be as efficient as BFS for finding the shortest path, but for educational purposes, it demonstrates another way to traverse the maze. We recursively explore each path, marking cells as visited and backtracking when dead-ends or exits are encountered.
This approach keeps a global minimum step count, updating it whenever an exit (that isn't the entrance) is found. Through recursive calls, each possible path is explored until all directions are exhausted. The main objective is to identify the closest exit with respect to steps taken from the entrance cell.
This C implementation of DFS explores each cell using recursive function calls. Directions are processed one by one, checking validity and boundary conditions for a potential exit. Dead-ends lead to recursive backtracking, unmarking visited cells to ensure every path combination is checked. The shortest path's steps are stored in a global variable, updated when an exit is found.
Time Complexity: O((m * n)^2) in the worst case, where m and n are dimensions of the maze.
Space Complexity: O(m * n) due to recursion stack usage in deep recursive path exploration.
We can start from the entrance and perform a breadth-first search (BFS). Each time we reach a new empty cell, we mark it as visited and add it to the queue until we find an empty cell on the boundary, then return the number of steps.
Specifically, we define a queue q, initially adding entrance to the queue. We define a variable ans to record the number of steps, initially set to 1. Then we start the BFS. In each round, we take out all elements from the queue and traverse them. For each element, we try to move in four directions. If the new position is an empty cell, we add it to the queue and mark it as visited. If the new position is an empty cell on the boundary, we return ans. If the queue is empty, we return -1. After this round of search, we increment ans by one and continue to the next round of search.
If we finish the traversal without finding an empty cell on the boundary, we return -1.
The time complexity is O(m times n), and the space complexity is O(m times n). Here, m and n are the number of rows and columns in the maze, respectively.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) Approach | Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the maze. In the worst case, all cells are traversed. |
| Depth-First Search (DFS) Approach | Time Complexity: O((m * n)^2) in the worst case, where m and n are dimensions of the maze. |
| BFS | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Breadth-First Search (BFS) | O(m*n) | O(m*n) | Best choice for shortest path in an unweighted grid or maze |
| Depth-First Search (DFS) | O(m*n) | O(m*n) | Useful for exploring all paths or practicing recursive grid traversal |
Nearest Exit from Entrance in Maze -(Samsung) : Explanation ➕ Live Coding • codestorywithMIK • 16,152 views views
Watch 9 more video solutions →Practice Nearest Exit from Entrance in Maze with our built-in code editor and test cases.
Practice on FleetCode