1926. Nearest Exit from Entrance in Maze
Problem Description
In this problem, we are given a maze represented by a 2D matrix. Each cell of the matrix can either be an empty cell ('.'
) or a wall ('+'
). An entrance to the maze is also given to us, specified by its row and column index. We are asked to find the shortest path from the entrance to the nearest exit of the maze. Here, an exit is defined as an empty cell located on the border of the maze, excluding the entrance itself. In each step, we can move to a cell that is adjacent (left, right, up, or down) to our current position, but we cannot move into walls or outside the maze boundaries.
Our goal is to navigate from the entrance to the nearest border cell (exit) by taking the fewest steps possible. If we can’t find any path to an exit, we must return -1
. The number of steps is counted as the minimum number of moves required to reach any exit from the entrance.
Flowchart Walkthrough
Let's utilize the algorithm flowchart to analyze LeetCode 1926. Nearest Exit from Entrance in Maze and determine the most suitable approach using the Flowchart. Here's a step-by-step walkthrough:
Is it a graph?
- Yes: The maze can be interpreted as a graph where each cell serves as a node, and edges exist between adjacent passages.
Is it a tree?
- No: The maze is not hierarchically structured as a tree and may include loops or multiple routes to a destination.
Is the problem related to directed acyclic graphs (DAGs)?
- No: The problem doesn't specify any directional constraints that prevent cycles, and loop backs are possible when wandering the maze.
Is the problem related to shortest paths?
- Yes: The task is to find the shortest path from an entrance to the nearest exit, classifying it as a shortest path problem.
Is the graph weighted?
- No: Moving from one maze cell to a neighboring cell is typically of equal cost, indicating an unweighted graph.
Conclusion: By following the flowchart steps, the most appropriate strategy for this unweighted, shortest path problem in a non-DAG structure is Breadth-First Search (BFS). This approach is well-suited to exploring levels of the maze systematically and finding the shortest route to the nearest exit.
Intuition
To solve this problem, we can use the Breadth-First Search (BFS) algorithm. BFS is an ideal choice for this kind of problem because it explores all possible paths level by level or, in this case, step by step from the entrance. As a result, the first time it reaches an exit, it is guaranteed to be the nearest one since BFS doesn't explore deeper paths until all paths of the current depth are explored.
We initialize BFS from the entrance by marking it as visited (to avoid revisiting) and then iteratively exploring all four adjacent cells. If an adjacent cell is empty and within the maze bounds, we check if it's an exit. If it's an exit, we immediately return the current step count since it's the minimum. If it's not, we continue the BFS by adding the cell to the queue. Importantly, as we enqueue a cell, we mark it with a wall to avoid revisiting cells that are already considered, effectively reducing unnecessary calculations.
If the BFS completes without finding an exit, we conclude that no path exists, and we return -1
, indicating failure to reach an exit.
Learn more about Breadth-First Search patterns.
Solution Approach
The solution provided uses the Breadth-First Search (BFS) algorithm to traverse through the maze. Let's dissect the given Python code to better understand how it translates the BFS strategy into a working solution.
1class Solution:
2 def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
3 m, n = len(maze), len(maze[0]) # Dimensions of the maze
4 i, j = entrance # Starting position (entrance of the maze)
5 q = deque([(i, j)]) # Initialize the queue with the entrance
6 maze[i][j] = '+' # Mark the entrance as visited by replacing it with '+'
7 ans = 0 # Steps counter
8 while q:
9 ans += 1 # Increment the step counter at the beginning of each level
10 for _ in range(len(q)): # Loop over every node in the current level
11 i, j = q.popleft() # Dequeue the front element from the queue
12 for a, b in [[0, -1], [0, 1], [-1, 0], [1, 0]]: # The 4 possible directions
13 x, y = i + a, j + b # Calculate the next cell's coordinates
14 if 0 <= x < m and 0 <= y < n and maze[x][y] == '.': # Check if it's within bounds and not visited
15 if x == 0 or x == m - 1 or y == 0 or y == n - 1: # Check if it's an exit
16 return ans # Return the current step count as the answer
17 q.append((x, y)) # Enqueue the cell for future exploration
18 maze[x][y] = '+' # Mark the cell as visited
19 return -1 # If the loop ends without finding an exit, return -1
Key Elements of the Solution:
-
Queue (
deque
): A queue is used for the BFS traversal, which follows the First-In-First-Out (FIFO) principle. This ensures that cells are explored in the order they are reached. -
Visited Marking: When a cell is visited, it is marked by changing its value to
'+'
. This prevents the algorithm from re-visiting the same cell, which would otherwise lead to infinite loops and incorrect step count. -
Direction Array: A simple 2D array
[[0, -1], [0, 1], [-1, 0], [1, 0]]
is used to represent the four possible moves from any cell (left, right, up, down). -
Checking Exit Condition: An exit is an empty cell (
'.'
) at the border of the maze. Whenever moving to a new cell, the algorithm checks if it is an exit by comparing its coordinates with the boundary of the maze. -
Steps Counter: The variable
ans
is used to count the number of steps taken to reach an exit. It gets incremented at the start of processing each level, ensuring the correct step count when an exit is found.
Efficiency of the Solution:
The solution is efficient for finding the shortest path in a maze scenario. BFS ensures that the first time we find an exit, it must be the closest one because we explore all possible paths of equal length before moving on to longer paths. The time and space complexity of this solution are both O(m*n), where m
is the number of rows and n
is the number of columns in the maze.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach. Consider the following 5x5 maze as an example, where E
is the entrance, .
represents an empty cell, and +
represents a wall:
1+ + + + + 2+ . . . + 3+ . E . + 4+ . . . + 5+ + + . +
Following the BFS strategy to navigate the maze from the entrance to the closest exit:
- Initialize the queue with the entrance coordinates, which is
(2, 2)
here, and set the starting cell as visited by marking it with '+':
1+ + + + + 2+ . . . + 3+ . + . + 4+ . . . + 5+ + + . +
- Process the first node in the queue, we explore its adjacent cells:
(2, 1)
,(2, 3)
,(1, 2)
, and(3, 2)
. These cells are not yet visited; we add them to the queue and mark them as visited:
1+ + + + + 2+ . + . + 3+ + + . + 4+ . + . + 5+ + + . +
-
We increment our steps counter
ans = 1
as we have started moving from the entrance. Now we process the cells in the queue. For each cell, we check its adjacent cells. For example, start with cell(2, 1)
and check(1, 1)
,(3, 1)
,(2, 0)
, and(2, 2)
. Here,(2, 0)
is not within the bounds,(2, 2)
is already visited, and(1, 1)
and(3, 1)
are available for further exploration. -
As we continue to explore the current level, we find that the cell
(1, 2)
is just one step away from an exit as it is located on the border of the maze. We've reached an exit:
1+ + + + + 2+ . + . + 3+ + + . + 4+ . + . + 5+ + + . +
- Since we've encountered an exit, we immediately return the current step count, which is
ans = 1
.
By the BFS approach, we've managed to find the nearest exit to the entrance in the fewest steps as possible without unnecessary calculations. If no exit had been reached, we would have continued to process the BFS queue until it was empty and then returned -1
to indicate no available exit.
Solution Implementation
1from collections import deque
2
3class Solution:
4 def nearest_exit(self, maze, entrance):
5 # Get the dimensions of the maze
6 rows, cols = len(maze), len(maze[0])
7
8 # Entrance coordinates
9 row_entrance, col_entrance = entrance
10
11 # Initialize a queue with the starting position (entrance)
12 queue = deque([(row_entrance, col_entrance)])
13
14 # Mark the starting position as visited by changing it to '+'
15 maze[row_entrance][col_entrance] = '+'
16
17 # Initialize the number of steps taken to exit
18 steps = 0
19
20 # Breadth-first search (BFS) loop
21 while queue:
22 # Increment the steps at the start of each level of BFS
23 steps += 1
24
25 # Go through each position at the current level
26 for _ in range(len(queue)):
27 # Get position from queue
28 row, col = queue.popleft()
29
30 # Directions in which we can move: left, right, up, down
31 directions = [[0, -1], [0, 1], [-1, 0], [1, 0]]
32
33 # Check all four directions
34 for direction_row, direction_col in directions:
35 # Calculate new position
36 new_row, new_col = row + direction_row, col + direction_col
37
38 # Check if the new position is within the maze boundaries
39 # and if it has not been visited (maze cell is '.')
40 if 0 <= new_row < rows and 0 <= new_col < cols and maze[new_row][new_col] == '.':
41 # Check if the new position is on the edge of the maze, which means an exit is found
42 if new_row == 0 or new_row == rows - 1 or new_col == 0 or new_col == cols - 1:
43 return steps
44
45 # Otherwise, add the position to the queue and mark as visited
46 queue.append((new_row, new_col))
47 maze[new_row][new_col] = '+'
48
49 # If we have not found an exit, return -1 indicating failure to find an exit
50 return -1
51
1class Solution {
2 public int nearestExit(char[][] maze, int[] entrance) {
3 // Maze dimensions
4 int rowCount = maze.length;
5 int colCount = maze[0].length;
6
7 // Queue for BFS
8 Queue<int[]> queue = new LinkedList<>();
9 queue.offer(entrance);
10
11 // Mark the entrance as visited
12 maze[entrance[0]][entrance[1]] = '+';
13
14 // Step count for nearest exit
15 int steps = 0;
16
17 // Directions for exploring neighbors (up, right, down, left)
18 int[] directions = {-1, 0, 1, 0, -1};
19
20 // Begin BFS
21 while (!queue.isEmpty()) {
22 steps++; // Increment steps at each level
23
24 for (int count = queue.size(); count > 0; count--) {
25 int[] currentPos = queue.poll(); // Poll the current position from the queue
26
27 // Iterate through all possible directions
28 for (int l = 0; l < 4; l++) {
29 int nextRow = currentPos[0] + directions[l];
30 int nextCol = currentPos[1] + directions[l + 1];
31
32 // Check if the next position is within bounds and not a wall
33 if (nextRow >= 0 && nextRow < rowCount && nextCol >= 0 && nextCol < colCount && maze[nextRow][nextCol] == '.') {
34 // Check if the next position is at the border, thus an exit
35 if (nextRow == 0 || nextRow == rowCount - 1 || nextCol == 0 || nextCol == colCount - 1) {
36 return steps; // Return the number of steps to reach this exit
37 }
38 // Mark the position as visited
39 queue.offer(new int[] {nextRow, nextCol});
40 maze[nextRow][nextCol] = '+';
41 }
42 }
43 }
44 }
45 // If no exit was found, return -1
46 return -1;
47 }
48}
49
1#include <vector>
2#include <queue>
3using namespace std;
4
5class Solution {
6public:
7 int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
8 // Initialize the maze dimensions
9 int rows = maze.size(), cols = maze[0].size();
10
11 // Queue to store the path in (x, y) coordinates
12 queue<vector<int>> queue{{entrance}};
13
14 // Mark the entrance as visited
15 maze[entrance[0]][entrance[1]] = '+';
16
17 // Initialize the step counter
18 int steps = 0;
19
20 // Possible directions to move: up, right, down, left
21 vector<int> directions = {-1, 0, 1, 0, -1};
22
23 // Perform breadth-first search to find the nearest exit
24 while (!queue.empty()) {
25 // Increment the step counter at the start of each level of BFS
26 ++steps;
27
28 // Process all nodes on the current level
29 for (int count = queue.size(); count > 0; --count) {
30 // Get the current position
31 auto position = queue.front();
32 queue.pop();
33
34 // Explore all possible directions from the current position
35 for (int i = 0; i < 4; ++i) {
36 int x = position[0] + directions[i], y = position[1] + directions[i + 1];
37
38 // Check if the new position is within bounds and not visited
39 if (x >= 0 && x < rows && y >= 0 && y < cols && maze[x][y] == '.') {
40 // Check if the new position is an exit
41 if (x == 0 || x == rows - 1 || y == 0 || y == cols - 1) return steps;
42
43 // Add the new position to the queue and mark as visited
44 queue.push({x, y});
45 maze[x][y] = '+';
46 }
47 }
48 }
49 }
50
51 // Return -1 if no exit is found
52 return -1;
53 }
54};
55
1interface Coordinates {
2 x: number;
3 y: number;
4}
5
6function nearestExit(maze: string[][], entrance: [number, number]): number {
7 // Initialize the maze dimensions
8 const rows = maze.length;
9 const cols = maze[0].length;
10
11 // Initialize a queue with the starting point containing x and y coordinates based on the entrance
12 const queue: Coordinates[] = [{ x: entrance[0], y: entrance[1] }];
13
14 // Mark the entrance as visited
15 maze[entrance[0]][entrance[1]] = '+';
16
17 // Initialize the step counter
18 let steps = 0;
19
20 // Possible directions to move: up, right, down, left (represented by x, y deltas)
21 const directions = [{ x: -1, y: 0 }, { x: 0, y: 1 }, { x: 1, y: 0 }, { x: 0, y: -1 }];
22
23 // Perform breadth-first search to find the nearest exit
24 while (queue.length > 0) {
25 // Increment the step counter at the start of each level of BFS
26 steps++;
27
28 // Process all nodes on the current level
29 for (let count = queue.length; count > 0; count--) {
30 // Get the current position by dequeueing from the front of the array
31 const position = queue.shift();
32
33 // Explore all possible directions from the current position
34 for (const direction of directions) {
35 const newX = position.x + direction.x;
36 const newY = position.y + direction.y;
37
38 // Check if the new position is within bounds and not visited
39 if (newX >= 0 && newX < rows && newY >= 0 && newY < cols && maze[newX][newY] === '.') {
40 // Check if the new position is an exit
41 if (newX === 0 || newX === rows - 1 || newY === 0 || newY === cols - 1) {
42 return steps;
43 }
44
45 // Add the new position to the queue and mark as visited
46 queue.push({ x: newX, y: newY });
47 maze[newX][newY] = '+';
48 }
49 }
50 }
51 }
52
53 // Return -1 if no exit is found
54 return -1;
55}
56
Time and Space Complexity
The time complexity of the given code is O(M*N)
, where M
is the number of rows and N
is the number of columns in the maze. This complexity arises because, in the worst-case scenario, the algorithm needs to traverse all the cells in the maze before finding an exit or determining that no exit is reachable. Traversal is done via breadth-first search (BFS), and each cell is visited at most once, as visited cells are marked with '+' to prevent revisiting.
The space complexity is also O(M*N)
due to the same reasoning. The space is used to store the queue q
, which, in the worst case, could contain all the cells as we explore the maze. Furthermore, we modify the maze to mark visited positions, which also takes O(M*N)
space; however, this does not add to the complexity as it is the same maze that is passed as input and not additional space being used.
Learn more about how to find time and space complexity quickly using problem constraints.
Which data structure is used to implement priority queue?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.