DFS Solution, Only successful DFS code till now. Explained.
A question which tells you dfs will not necessarily give you the shortest path. \n*\nMy thinking: Firstly I applied only dfs, it gave me a TLE. Next I tried to 
### A question which tells you dfs will not necessarily give you the shortest path. \n****\nMy thinking: Firstly I applied only dfs, it gave me a TLE. Next I tried to optimize it using memoization as there could be a possiblity of revisiting a cell multiple times. Final test case was not giving me the correct output, after some analysing the final test case of memoization + dfs, I found out that it was giving the corect output for only dfs. **DFS will not give the shortest path in an unweighted graph like structure** , that\'s the key note. You can have a look over this article [here](hhttps://cs.stackexchange.com/questions/4914/why-cant-dfs-be-used-to-find-shortest-paths-in-unweighted-graphs#:~:text=Assign%20edges%20(s%2Ct),paths%20(in%20general%20graphs).ttp://).\n\nCode :\n\n```\nclass Solution {\n    int a, b;\n    Integer[][] dp;\n    public int nearestExit(char[][] maze, int[] entrance) {\n        int i = entrance[0];\n        int j = entrance[1];\n        a = i;\n        b = j;\n        dp = new Integer[maze.length + 1][maze[0].length + 1];\n        if (maze.length < 20 && maze[0].length < 15) {\n            int ans1 = dfs1(maze, i, j);\n            if (ans1 >= (int)1e9) return -1;\n            return ans1;\n        }\n        \n        else {\n            int ans = dfs(maze, i, j);\n            if (ans >= (int)1e9) return -1;\n            return ans;\n        }\n    }\n    int dfs(char[][] maze, int i, int j) {\n        \n        if (i < 0 || j < 0 || j >= maze[0].length || i >= maze.length || maze[i][j] == \'+\') return (int)1e9;\n        if (dp[i][j] != null) return dp[i][j];\n        if ((i == 0 || j == 0 || i == maze.length - 1 || j == maze[0].length - 1) && (maze[i][j] == \'.\') && (i != a || j != b)) return 0;\n\n        \n        maze[i][j] = \'+\';\n        int right = 1 + dfs(maze,i, j + 1);\n        int left = 1 + dfs(maze,i, j - 1);\n        int up = 1 + dfs(maze,i - 1, j);\n        int down = 1 + dfs(maze,i + 1, j);\n        maze[i][j] = \'.\';\n        return dp[i][j] = Math.min(Math.min(up, down), Math.min(left, right));\n    }\n    int dfs1(char[][] maze, int i, int j) {\n        if (i < 0 || j < 0 || j >= maze[0].length || i >= maze.length || maze[i][j] == \'+\') return (int)1e9;\n\n        if ((i == 0 || j == 0 || i == maze.length - 1 || j == maze[0].length - 1) && (maze[i][j] == \'.\') && (i != a || j != b)) return 0;\n        \n        maze[i][j] = \'+\';\n        int right = 1 + dfs1(maze,i, j + 1);\n        int left = 1 + dfs1(maze,i, j - 1);\n        int up = 1 + dfs1(maze,i - 1, j);\n        int down = 1 + dfs1(maze,i + 1, j);\n        maze[i][j] = \'.\';\n        return Math.min(Math.min(up, down), Math.min(left, right));\n    }\n}\n```\n\nThe code itself is very explanatory, but what\'s the keynote is that if you want to try dfs for shortest path type question you might have to brainstorm hard might end up writing code like above, while bfs is short, clean and concise.\n\n*So the bottom line is USE BFS FOR SHORTEST PATH TYPE QUESTIONS !*
['Depth-First Search', 'Java']