[python3] BFS (2 styles) with line by line comments O(m*n)
BFS is more suitable for searching vertices closer to the given source. BFS is optimal for finding the shortest path.\n- DFS is more suitable when there are sol
- BFS is more suitable for searching vertices closer to the given source. BFS is optimal for finding the shortest path.\n- DFS is more suitable when there are solutions away from the source. DFS is not optimal for finding the shortest path.\n\nSo we chose BFS over DFS for this problem of finding the shortest path.\n\n**Style 1** Using ```maze``` to track visited positions and store the steps for each position inside the q.\n```python\nclass Solution:\n    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:\n        ### Get the maze size, used later to check whether the neighbor is valid.\n        m,n = len(maze),len(maze[0])\n        \n        ### The directions that we can go at each position.\n        directions = [[0,1],[1,0],[0,-1],[-1,0]]\n        \n        ### We use deque to make the pop more efficient\n        ### We also have the steps stored at each position, and at any time, \n        ### if we see an exit, we simply return the steps.\n        ### Note that if you don\'t put the steps along with the positions, \n        ### you will need to keep track of the levels you are at during the search (see style2).\n        q = deque([[entrance[0],entrance[1],0]])\n        \n        ### We don\'t need to use extra space to store the visited positions, \n        ### since we can directly change the empty position in the maze to a wall.\n        maze[entrance[0]][entrance[1]] = \'+\'\n        \n        ### Doing a regular BFS search using deque; if there is anything left in the q, we will keep doing the search\n        while q:\n            ### Pop form left of the q,\n            ### Since we have steps stored at each position, we don\'t need to make a loop here (see style2 for the loop version).\n            xo,yo,steps = q.popleft()\n            \n            ### Check if the current location is an exit, and make sure it is not the entrance.\n            if (0 in [xo,yo] or xo==m-1 or yo==n-1) and [xo,yo]!=entrance:\n                return steps\n            \n            ### We go in four directions.\n            for xn,yn in directions:\n                x,y = xo+xn,yo+yn\n                ### Make sure the new location is still inside the maze and empty.\n                if 0<=x<m and 0<=y<n and maze[x][y]==\'.\':\n                    ### We make the empty space into a wall, so we don\'t visit it in the future.\n                    maze[x][y] = \'+\'\n                    ### We need to increase the steps.\n                    q.append([x,y,steps+1])\n        \n        ### If we don\'t find the result in BFS, we need to return -1\n        return -1\n```\n\n**Style 2** Using extra space for the visited positions and tracking steps using an extra variable (level by level search)\n```python\nclass Solution:\n    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:\n        \n        m,n = len(maze),len(maze[0])\n        directions = [[0,1],[1,0],[0,-1],[-1,0]]\n        q = deque([entrance])\n        \n        ### Using extra space to keep track of the visited positions.\n        visited = {tuple(entrance)}\n        \n        ### Use steps to keep track of the level of the BFS.\n        steps = 0\n        while q:\n            \n            ### Since we are tracking the steps using a variable, \n            ### we need to pop all elements at each level, then increase the steps.\n            for _ in range(len(q)):\n                xo,yo = q.popleft()\n                if (0 in [xo,yo] or xo==m-1 or yo==n-1) and [xo,yo]!=entrance:\n                    return steps\n                for xn,yn in directions:\n                    x,y = xo+xn,yo+yn\n                    ### Check if the new position has been visited or not., and only go into the unvisited ones.\n                    if 0<=x<m and 0<=y<n and maze[x][y]==\'.\' and (x,y) not in visited:\n                        visited.add((x,y))\n                        q.append([x,y])\n            ### Increase the steps since we finished one level.\n            steps += 1\n        \n        return -1\n```\n\nBoth styles work fine for this problem, but I prefer the first style for this problem, or more generally, I prefer to use the first one if I need to find some distance, e.g., **[The Maze](https://leetcode.com/problems/the-maze/)**. Style1 can be easily converted into **DFS** or **Dijkstra\'s algorithm**. So it is good to know this style!\n\nThe second style is more preferred, or you have to use it when you are asked to do something at each level during the search, such as this problem **[Reverse Odd Levels of Binary Tree](https://leetcode.com/problems/reverse-odd-levels-of-binary-tree/discuss/2590130/python3-bfs-and-dfs-with-line-by-line-comments)**. Give them a try if you want to practice more on BFS. \n\nThese are just my opinion; leave a comment below to let me know if you agree or disagree.\n\n**Upvote** if you like this post.\n\n**Connect with me on [LinkedIn](https://www.linkedin.com/in/meida-chen-938a265b/)** if you\'d like to discuss other related topics\n\n\uD83C\uDF1F If you are interested in **Machine Learning** || **Deep Learning** || **Computer Vision** || **Computer Graphics** related projects and topics, check out my **[YouTube Channel](https://www.youtube.com/@meidachen8489)**! Subscribe for regular updates and be part of our growing community.
[]