[Python] Easy DFS MEMOIZATION & BFS
Nearest Exit from Entrance in Maze\n## DFS Idea\n We search from entrance cell for the nearest boundary cell in all four directions and after getting the distan
# **Nearest Exit from Entrance in Maze**\n## DFS Idea\n* We search from entrance cell for the nearest boundary cell in all four directions and after getting the distance from all direction, it returns *minimum* of them.\n* Function `reached` checks if currect cell is boundary and not the entrance cell\n* Here `@lru_cache(None)` is used for top-down memoization approach\n\n**Complexity**\n* Time Complexity :- `O(m*n)`\n* Space Complexity :- `O(m*n)` because of  `@lru_cache(None)`\n\n```\nclass Solution:\n    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:\n        x, y = entrance\n        m, n, infi = len(maze), len(maze[0]), int(1e5)\n        reached = lambda p, q: (not p==x or not q==y) and (p==0 or q==0 or p==m-1 or q==n-1)\n        @lru_cache(None)\n        def dfs(i, j):\n            if i<0 or j<0 or i==m or j==n or maze[i][j]==\'+\':\n                return infi\n            if reached(i, j):\n                return 0\n            maze[i][j] = \'+\'\n            ans = 1+min(dfs(i+1, j), dfs(i-1, j), dfs(i, j+1), dfs(i, j-1))\n            maze[i][j] = \'.\'\n            return ans\n        ans = dfs(x, y)\n        return -1 if ans>=infi else ans\n```\n*why DFS with dp sometimes give WA explained in the end*.\n\n## BFS Idea\n* We search from entrance cell for the nearest boundary cell in all four directions level by level i.e. 0, 1.... until we get boundary\n* Function `reached` checks if currect cell is boundary and not the entrance cell\n\n**Complexity**\n* Time Complexity :- `O(m*n)`\n* Space Complexity :- `O(m*n)`\n\n```\nclass Solution:\n    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:\n        x, y = entrance\n        m, n, infi = len(maze), len(maze[0]), int(1e5)\n        reached = lambda p, q: (not p==x or not q==y) and (p==0 or q==0 or p==m-1 or q==n-1)\n        q, ans = deque(), 0\n        q.append((x, y, ans))\n        directions = [1, 0, -1, 0, 1]\n        while q:\n            row, col, ans = q.popleft()\n            for i in range(4):\n                r, c = row+directions[i], col+directions [i+1]\n                if r<0 or c<0 or r==m or c==n or maze[r][c]==\'+\':\n                    continue\n                if reached(r, c):\n                    return ans+1\n                maze[r][c] = \'+\'\n                q.append((r, c, ans+1))\n        return -1\n```\n\n**Why DFS with Memoization sometimes gives WA**:-.\n\nFor **DFS without memoization** all test case will give correct answer as it search every path but may give **TLE**, and for **DFS with dp** it totally depends on luck , what you search first.\nFor better understanding let\'s take example:-\n\n**e** denotes Entrance\n```\n++++\n.e.+\n.+.+\n...+\n++++\n```\n`Condition -> 1+min((i, j+1), .............)`\nAfter operations it will look like\n```\n++++\n7e1+\n6+2+\n543+\n++++\n```\n`ans = 1+min(7, 7, infinite, infinite)`\ninstead of \n`ans = 1+min(7, 1, infinite, infinite)`\n\n[Note] => *This example is just for intuition. For real example please see https://github.com/LeetCode-Feedback/LeetCode-Feedback/issues/4115*\n\n**Conclusion**:-\n* DFS without memoization works fine but gives TLE\n* DFS with memoization may give correct but not necessary\n* BFS searches level wise and gives result as soon as finds exit which is best for this problem\n\n*Please upvote if you like the solution and comment if have queries*
['Depth-First Search', 'Breadth-First Search', 'Memoization', 'Python']