Solution: Nearest Exit from Entrance in Maze

Grokking Graph Algorithms for Coding Interviews

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Nearest Exit from Entrance in Maze

Table of Contents

Contents are not accessible

Problem Statement

You are given a maze of size m x n as a 2D grid with walls and open spaces. The walls are marked as '+', and the open spaces are marked as '.'. You also have an entrance point of the maze, where entrance = [entrancerow, entrancecol] denotes the row and column of the cell you are initially standing at.

You can start the movement from the entrance, and in a single step, you can move up, down, left, or right into another open space. You can't move to the cell having a wall or outside of the maze.

Find the shortest path from the entrance to any exit. An exit is an open space at the border of the maze. Note that the entrance is not considered an exit.

Return the number of steps in the shortest path from the entrance to the nearest exit. If there is no way to reach an exit, return -1.

Examples

Example 1

Input: entrance = [1,2], maze =

[["+","+","+","+"],
 [".",".",".","+"],
 [".",".","+","."]]

Expected Output: 2

Explanation: Starting at (1,2), you can move to (1,1), and from (1, 1), you can either move to (1, 0) or (2, 1), which is an exit.

Example 2

Input: entrance = [0,0], maze =

[[".",".",".","+"],
 ["+","+",".","+"],
 ["+","+","+","."],
 ["+","+","+","."]]

Expected Output: 1

Explanation: Starting at (0,0), you move to (1,0), reaching an exit at the bottom border.

Example 3

Input: entrance = [0,2], maze =

[["+","+",".","+"],
 ["+","+","+","."]]

Expected Output: -1
Explanation: The entrance is already at the border but does not count as an exit, and there are no other reachable exits.

Constraints:

maze.length == m
maze[i].length == n
1 <= m, n <= 100
maze[i][j] is either '.' or '+'.
entrance.length == 2
0 <= entrancerow < m
0 <= entrancecol < n
entrance will always be an empty cell.

Solution

To solve this problem, we will use the Breadth-First Search (BFS) algorithm. BFS is well-suited for finding the shortest path in an unweighted grid like this maze. The BFS algorithm explores all possible moves level by level, ensuring that we find the shortest path to the nearest exit first. We will use a queue to keep track of our current position and the number of steps taken to reach that position. As we explore each cell, we will mark it as visited to avoid revisiting it.

This approach guarantees that once we reach an exit, it will be via the shortest path possible due to the nature of BFS.

Step-by-Step Algorithm

Initialize Variables:
- Get the number of rows and columns in the maze.
- Define the possible directions for movement: right, down, left, up.
- Initialize a queue for BFS and add the entrance position to it with step count as 0.
- Mark the entrance cell as visited by changing its value to '+'.
BFS Loop:
- While the queue is not empty, do the following:
  - Dequeue the current position from the queue.
  - For each possible direction, calculate the new row and column.
  - Check if the new position is within the maze boundaries and is an open space ('.'):
    - If the new position is at the border of the maze and not the entrance, return the current steps + 1.
    - Otherwise, add the new position to the queue with the incremented step count and mark it as visited by changing its value to '+'.
No Exit Found:
- If the queue is empty and no exit was found, return -1.

Algorithm Walkthrough

Let's use the entrance [1, 2] and the maze:

[["+","+","+","+"],
 [".",".",".","+"],
 [".",".","+","."]]

Initialization:
- rows = 3
- cols = 4
- directions = [[0,1],[1,0],[0,-1],[-1,0]]
- queue = [(1, 2, 0)] (entrance position with step count 0)
- Mark the entrance as visited: maze[1][2] = '+'
Maze now looks like:
```
[["+","+","+","+"],
 [".",".","+","+"],
 [".",".","+","."]]
```
First Iteration:
- Dequeue (1, 2, 0):
  - Current position: (1, 2)
  - Current steps: 0
- Explore all directions:
  - Right: (1, 3) (not open, skip)
  - Down: (2, 2) (not open, skip)
  - Left: (1, 1) (open, within bounds)
    - Add (1, 1, 1) to queue and mark as visited.
  - Up: (0, 2) (not open, skip)
Maze now looks like:
```
[["+","+","+","+"],
 [".","+","+","+"],
 [".",".","+","."]]
```
Queue: [(1, 1, 1)]
Second Iteration:
- Dequeue (1, 1, 1):
  - Current position: (1, 1)
  - Current steps: 1
- Explore all directions:
  - Right: (1, 2) (already visited, skip)
  - Down: (2, 1) (open, reached to the boundary).
    - This is an open space at the border of the maze, so return steps + 1 = 2.

Code

Python3

. . . .

Complexity Analysis

Time Complexity: The time complexity of this algorithm is $O(m \times n)$ , where (m) is the number of rows and (n) is the number of columns in the maze. This is because in the worst case, every cell in the maze is visited once.
Space Complexity: The space complexity is $Omax(m, n)$ due to the additional space required for the queue. It can hold up to $max(m, n)$ positions in the worst case.

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible