We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Nearest Exit from Entrance in Maze

Number: 2038

Difficulty: Medium

Paid? No

Companies: Meta, Amazon, Google, Microsoft, eBay, Uber

Problem Description

Given a maze represented by an m x n matrix with empty cells ('.') and walls ('+'), and a starting position (entrance), find the minimum number of steps required to reach the nearest exit from the maze. An exit is any empty cell located on the maze border (excluding the entrance itself). You can move up, down, left, or right in one step. If no exit exists, return -1.

Key Insights

  • The problem requires finding the shortest path in an unweighted grid, which suggests using Breadth-First Search (BFS).
  • Since all movements have the same cost, BFS guarantees the minimum steps to reach an exit.
  • We need to carefully treat the entrance cell and avoid revisiting cells by marking them as visited.
  • Border cells (other than the entrance) are considered valid exits.

Space and Time Complexity

Time Complexity: O(m * n) where m and n are the number of rows and columns respectively. Space Complexity: O(m * n) due to the queue and visited structure in the worst-case scenario.

Solution

We solve the problem using the Breadth-First Search (BFS) algorithm. Starting from the entrance, we systematically explore all reachable cells in layers. For each cell, we check its four possible adjacent positions (up, down, left, right). If an adjacent cell is within bounds, is not a wall, and has not been visited, we add it to the queue for further exploration. We also check if the cell is on the border (and is not the entrance) to determine if it is an exit. The first time we reach such a cell, we return the number of steps taken. If the queue is exhausted without finding an exit, we return -1.

Code Solutions

from collections import deque

def nearestExit(maze, entrance):
    # Get maze dimensions
    rows, cols = len(maze), len(maze[0])
    # Directions for up, down, left, and right moves
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    # BFS queue initialized with entrance and 0 steps taken so far
    queue = deque([(entrance[0], entrance[1], 0)])
    # Mark the entrance as visited by using a set or modifying the maze in place
    maze[entrance[0]][entrance[1]] = '+'
    
    while queue:
        r, c, steps = queue.popleft()
        # Check all four possible directions
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            # Check if the new position is within bounds and not a wall
            if 0 <= nr < rows and 0 <= nc < cols and maze[nr][nc] == '.':
                # If the new cell is at the border, it is an exit (but ensure it is not the entrance)
                if nr == 0 or nr == rows - 1 or nc == 0 or nc == cols - 1:
                    return steps + 1
                # Mark cell as visited and add to queue
                maze[nr][nc] = '+'
                queue.append((nr, nc, steps + 1))
    # No exit found
    return -1

# Example usage:
# maze = [["+", "+", ".", "+"], [".", ".", ".", "+"], ["+", "+", "+", "."]]
# entrance = [1, 2]
# print(nearestExit(maze, entrance))
← Back to All Questions