✅✅✅ 614 ms, faster than 98.64% of Python3 || Easy to Understand
\n\n# Intuition\nThe maze consists of open spaces (\'.\') and walls (\'+\'). An exit is defined as any open space located at the boundary of the maze, excluding
![\u0421\u043D\u0438\u043C\u043E\u043A \u044D\u043A\u0440\u0430\u043D\u0430 2024-05-24 \u0432 17.09.15.png](https://assets.leetcode.com/users/images/610e0cd8-7c7a-4cf6-9b1c-5bae67df53db_1716585777.35953.png)\n\n# Intuition\nThe maze consists of open spaces (\'.\') and walls (\'+\'). An exit is defined as any open space located at the boundary of the maze, excluding the entrance itself. The goal is to use a **breadth-first search (BFS)** to explore the shortest path from the entrance to the nearest exit.\n\n# Approach\nTo solve this problem, we can use the **BFS** **algorithm**, which is well-suited for finding the shortest path in an unweighted grid. BFS will explore all possible moves level by level, ensuring that we find the shortest path to the nearest exit.\n1.\tInitialize a queue with the entrance position and a step counter set to 0.\n2.\tMark the entrance as visited by replacing the value at the entrance position with \'+\'.\n3.\tWhile the queue is not empty, dequeue the front element to get the current position and step count.\n4.\tFor each of the four possible directions (up, down, left, right), calculate the new position.\n5.\tIf the new position is within the maze bounds and is an open space (\'.\'), check if it is on the boundary of the maze.\n- If it is on the boundary, return the current step count plus one as the result.\n- Otherwise, mark the new position as visited and enqueue it with the incremented step count.\n6.\tIf the queue is exhausted without finding an exit, return -1.\n\n# Complexity\n- Time complexity: ***O(m x n)***\nThe time complexity of the algorithm is *O(m x 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, we may need to visit every cell in the maze.\n\n- Space complexity: ***O(max(m, n))***\n\n# Code\n```\nfrom collections import deque\n\nclass Solution:\n    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:\n        m = len(maze)\n        n = len(maze[0])\n\n        queue = deque([(entrance[0], entrance[1], 0)]) # step 1\n        maze[entrance[0]][entrance[1]] = "+" # step 2\n\n        while queue:\n            row, col, steps = queue.popleft() # step 3\n\n            for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]: # step 4\n                nr, nc = row + dy, col + dx\n                if 0 <= nr < m and 0 <= nc < n and maze[nr][nc] == ".": # step 5\n                    if (nr == 0 or nr == m - 1) or (nc == 0 or nc == n - 1):\n                        return steps + 1\n\n                    maze[nr][nc] = "+"\n                    queue.append((nr, nc, steps + 1))\n\n        return -1 # step 6\n            \n        \n```
['Breadth-First Search', 'Queue', 'Python3']