Python 3 | BFS, Deque, In-place | Explanation
Explanation\n- Use BFS to find shortest/closest\n- Starting from entrance, if you see a . on the boarder and it\'s not the entrance, then that\'s a exit\n- Mark
### Explanation\n- Use `BFS` to find shortest/closest\n- Starting from `entrance`, if you see a `.` on the boarder and it\'s not the entrance, then that\'s a exit\n- Mark visited place as `+` to avoid revisit (also we don\'t need to use a `visisted = set()` here)\n- We pass a 3rd parameter as the `step` we need to reach a certain place. Return this step when exit is found\n- A very similar question to this is [1730. Shortest Path to Get Food](https://leetcode.com/problems/shortest-path-to-get-food/)\n- Time: `O(m*n)`, `m, n` is the dimension of `maze`\n- Space: `O(m*n)`\n### Implementation\n```\nclass Solution:\n    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:\n        q = collections.deque([(*entrance, 0)])\n        m, n = len(maze), len(maze[0])\n        maze[entrance[0]][entrance[1]] == \'+\'    \n        while q:\n            x, y, c = q.popleft()\n            if (x == 0 or x == m-1 or y == 0 or y == n-1) and [x, y] != entrance:\n                return c\n            for i, j in [(x+_x, y+_y) for _x, _y in [(-1, 0), (1, 0), (0, -1), (0, 1)]]:\n                if 0 <= i < m and 0 <= j < n and maze[i][j] == \'.\':\n                    maze[i][j] = \'+\'\n                    q.append((i, j, c + 1))\n        return -1\n```
['Breadth-First Search', 'Queue', 'Python', 'Python3']