Problem Statement: You are given an m x n maze. You are initially positioned at the entrance of the maze (0, 0). Your goal is to reach the exit of the maze (m-1, n-1) which could be a different tile from the entrance. You can only move either up, down, left, or right at a time. You cannot move diagonally. You cannot move out of the maze. The maze is represented by an m x n binary matrix. 1 means the tile is a wall and you cannot pass through it, and 0 means the tile is empty and you can walk on it. The maze is guaranteed to have exactly one entrance and one exit.

Solution: To solve this problem, we can use BFS (Breadth First Search) algorithm. We will keep a queue of cells that we need to explore. We will start by adding the entrance cell to the queue. We will also keep a visited set which will mark all the cells that we have already visited. At each step, we will check all the neighboring cells (top, bottom, left, right) and add them to the queue if they are valid and have not been visited. We will repeat this process until we reach the exit. We will also keep track of the distance traveled from the entrance to each cell.

Algorithm:

1. Create a queue and add the entrance cell to it.
2. Create a set of visited cells and mark the entrance cell as visited.
3. Create a dictionary to store the distance traveled from entrance to each cell.
4. While the queue is not empty, repeat the following steps: a. Dequeue the first cell from the queue. b. Check if the dequeued cell is the exit cell, if yes then return its distance from the entrance. c. For each neighboring cell that is valid and not visited, add it to the queue and mark it as visited. Also, update its distance traveled from the entrance.
5. If we reach here, then the exit cell is not reachable from the entrance cell, so return -1.

Python Code:

from collections import deque

def nearestExit(maze, entrance): # Get maze dimensions m, n = len(maze), len(maze[0]) # Create a queue for BFS queue = deque([(entrance[0], entrance[1], 0)]) # Create a set of visited cells visited = set([(entrance[0], entrance[1])]) # Create a dictionary to store distance traveled from the entrance to each cell dist = {(entrance[0], entrance[1]): 0} # Loop until queue is not empty while queue: i, j, d = queue.popleft() # Check if we have reached the exit cell if (i == 0 or i == m-1 or j == 0 or j == n-1) and (i, j) != entrance: return d # Visit the neighboring cells for di, dj in [(0,1),(1,0),(0,-1),(-1,0)]: ni, nj = i+di, j+dj if 0 <= ni < m and 0 <= nj < n and maze[ni][nj] == 0 and (ni, nj) not in visited: queue.append((ni, nj, d+1)) visited.add((ni, nj)) dist[(ni, nj)] = d+1 # If we reach here, the exit cell is not reachable from the entrance cell return -1

Driver code

maze = [[0,0,0,0,0,0], [1,1,0,0,1,1], [0,0,0,0,0,0], [0,1,1,1,1,0], [0,1,1,1,0,0], [0,0,0,0,0,0]] entrance = (2,0) print(nearestExit(maze, entrance)) # Output: 8

Complexity Analysis:

• Time Complexity: O(mn) where mn is the size of the maze.
• Space Complexity: O(mn) where mn is the size of the maze.

1