✅ [Python/C++] DFS sucks here, go BFS (explained)
\u2705 IF YOU LIKE THIS SOLUTION, PLEASE UPVOTE.\n*\nThis solution employs Breadth First Search* approach to explore the maze. Time complexity is linear: O(m\n)
**\u2705 IF YOU LIKE THIS SOLUTION, PLEASE UPVOTE.**\n****\nThis solution employs *Breadth First Search* approach to explore the maze. Time complexity is linear: **O(m\\*n)**. Space complexity is linear: **O(m\\*n)**. \n****\n\n**Comment.** This problem can be solved by using both BFS and DFS, however, the latter seems to be  a significantly slower approach. It is also important to mark visited cells when they are added to (and not popped from) the queue, check this [**explanation**](https://leetcode.com/problems/nearest-exit-from-entrance-in-maze/discuss/1329445/An-analysis-on-Time-Limit-Exceeded-(TLE)).\n\n**Python #1.** Fast BFS solution.\n```\nclass Solution:\n    def nearestExit(self, maze: List[List[str]], e: List[int]) -> int:\n        \n        m, n = len(maze), len(maze[0])\n        x, y = e\n        \n        # this lambda checks the exit condition \n        is_exit = lambda i, j : i*j==0 or i==m-1 or j==n-1\n        \n        # this generator yields (!) allowed directions\n        def adj(i,j, dirs=[1, 0, -1, 0, 1]):\n            for d in range(4):\n                ii, jj = i + dirs[d], j + dirs[d+1]\n                if 0 <= ii < m and 0 <= jj < n and maze[ii][jj] != "+":\n                    yield ii,jj\n            \n        dq = deque([(x,y,0)])                      # [1] start from the entrance...\n        maze[x][y] = \'+\'                           #     ...and mark it as visited\n        while dq:                                  # [2] while there are still places to go...\n            i, j, s = dq.popleft()                 #     ...try going there (don\'t try, do it!)\n            for ii,jj in adj(i,j):                 # [3] look around, make a step...\n                maze[ii][jj] = "+"                 #     ...and mark it as visited\n                if is_exit(ii,jj) : return s+1     # [4] great, it\'s the exit!\n                dq.append((ii,jj,s+1))             # [5] or maybe not, continue searching\n                \n        return -1                                  # [6] BFS failed, there is no escape\n```\n\n**Python #2.** Crappy DFS solution that gives TLE.\n```\nclass Solution:\n    def nearestExit(self, maze: List[List[str]], e: List[int]) -> int:\n        \n        m, n = len(maze), len(maze[0])\n        \n        is_exit = lambda i, j : (i!=e[0] or j!=e[1]) and (i*j==0 or i==m-1 or j==n-1)\n\n        def adj(i,j, dirs=[1, 0, -1, 0, 1]):\n            for d in range(4):\n                ii, jj = i + dirs[d], j + dirs[d+1]\n                if 0 <= ii < m and 0 <= jj < n and maze[ii][jj] != "+":\n                    yield ii,jj\n                    \n        @lru_cache(None)\n        def dfs(i, j, s = 0):\n            if is_exit(i,j) : return s\n            maze[i][j] = "+"\n            dp = [dfs(ii, jj, s+1) for ii,jj in adj(i,j)] or [inf]\n            maze[i][j] = "."\n            return min(dp)\n                        \n        return s if (s:=dfs(e[0], e[1])) < inf else -1\n```\n\nBFS solution in other languages.\n\n<iframe src="https://leetcode.com/playground/knSTh8vg/shared" frameBorder="0" width="800" height="650"></iframe>
[]