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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Nearest Exit from Entrance in Maze

Difficulty: Medium

Problem Description

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 = [entrance_row, entrance_col] 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.

Key Insights

  • The problem can be visualized as a graph traversal where each cell is a node.
  • The BFS (Breadth-First Search) algorithm is suitable for finding the shortest path in an unweighted grid.
  • Exits are defined as empty cells located at the borders of the maze, excluding the entrance cell.
  • Care should be taken to mark visited cells to avoid cycles and unnecessary computations.

Space and Time Complexity

Time Complexity: O(m * n)
Space Complexity: O(m * n)

Solution

To solve this problem, we use the Breadth-First Search (BFS) algorithm. We start from the entrance cell and explore all four possible directions (up, down, left, right) to find the nearest exit.

  1. Create a queue to keep track of the cells to explore, starting with the entrance cell.
  2. Maintain a set or a matrix to track visited cells to avoid re-processing.
  3. For each cell, check if it is a valid exit (i.e., it is on the border and is not the entrance).
  4. If an exit is found, return the number of steps taken to reach it.
  5. If the queue is exhausted and no exit is found, return -1.

Code Solutions

from collections import deque

def nearestExit(maze, entrance):
    rows, cols = len(maze), len(maze[0])
    queue = deque([entrance])
    visited = set([tuple(entrance)])
    steps = 0
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    
    while queue:
        for _ in range(len(queue)):
            x, y = queue.popleft()
            # Check if it's an exit (not the entrance)
            if (x != entrance[0] or y != entrance[1]) and (x == 0 or x == rows - 1 or y == 0 or y == cols - 1):
                return steps
            
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < rows and 0 <= ny < cols and maze[nx][ny] == '.' and (nx, ny) not in visited:
                    visited.add((nx, ny))
                    queue.append((nx, ny))
        
        steps += 1
    
    return -1
← Back to All Questions