Problem of The Day: Nearest Exit from Entrance in Maze

Problem Statement

leetcode problem link

BFS Approach [Accepted]

class Solution:
    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
        ROWS = len(maze)
        COLS = len(maze[0])
        directions = [(0,1),(0,-1),(1,0),(-1,0)]
        res = float('inf')

        queue = deque()
        queue.append([entrance[0],entrance[1], 0])
        while queue:
            row, col, level = queue.popleft()
            maze[row][col] =  '+'
            if (row in (0, ROWS - 1) or col in (0, COLS - 1)) and level > 0:
                res = min(res, level)
                continue
            for x, y in directions:
                next_row, next_col = row + x, col + y
                if 0 <= next_row < ROWS and 0 <= next_col < COLS \
                    and maze[next_row][next_col] == '.':
                    maze[next_row][next_col] =  '+'
                    queue.append([next_row, next_col, level + 1])

        return res if res != float('inf') else -1

Editorial

Approach: Breadth First Search (BFS)

class Solution:
    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
        rows, cols = len(maze), len(maze[0])
        dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))

        # Mark the entrance as visited since its not a exit.
        start_row, start_col = entrance
        maze[start_row][start_col] = "+"

        # Start BFS from the entrance, and use a queue `queue` to store all
        # the cells to be visited.
        queue = collections.deque()
        queue.append([start_row, start_col, 0])

        while queue:
            curr_row, curr_col, curr_distance = queue.popleft()

            # For the current cell, check its four neighbor cells.
            for d in dirs:
                next_row = curr_row + d[0]
                next_col = curr_col + d[1]

                # If there exists an unvisited empty neighbor:
                if 0 <= next_row < rows and 0 <= next_col < cols \
                    and maze[next_row][next_col] == ".":

                    # If this empty cell is an exit, return distance + 1.
                    if 0 == next_row or next_row == rows - 1 or 0 == next_col or next_col == cols - 1:
                        return curr_distance + 1

                    # Otherwise, add this cell to 'queue' and mark it as visited.
                    maze[next_row][next_col] = "+"
                    queue.append([next_row, next_col, curr_distance + 1])

        # If we finish iterating without finding an exit, return -1.
        return -1