Easy DFS With Memoization! Beginner Friendly C++ with intuition!!
Intuition\n Describe your first thoughts on how to solve this problem. \nWe need to check all paths and return true if in any path we reach destination with hea
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe need to check all paths and return true if in any path we reach destination with health intact. Therefore to check all paths we need to have a recursive approach, i.e., DFS. Now in a grid we do have overlapping sub-problems, therefore we can optimise it with dynamic programming.\n\n# Approach\nFirst of all, check if the starting grid itself is an obstacle then reduce the health by 1(I fumbled on this!).\nMake the dp 3D grid where 2D will be your position in grid and the added dimension is for various health levels you might have when you reach there. Make a visited grid as well.\n\nNow call the recursive conditions. Write the base case and check if you have previously solved this sub problem. If yes, return the answer. If not, then you can go to 4 directions from any point. Check whether it is safe to go to that position. If yes, then check if that has obstacle and if it has then reduce the health by 1. If the recursive call returns true thn propagate it. \nIf after doing everything you come out of loop, mark the cell as unvisited and return false as you did not reach location from this path.\n<!-- Describe your approach to solving the problem. -->\n\n**Please Upvote if you find it useful!**\n\n# Complexity\n- Time complexity: O(M*N)*4\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(M*N*H) + O(M*N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\n    bool safe(int i, int j, int m, int n, vector<vector<int>>& visited) {\n        if(i<0 || j<0 || i>=m || j>= n || visited[i][j] == 1) return false;\n        return true;\n    }\n    bool walk(int x, int y, vector<vector<int>>& grid, int health, int m, int n, \n    vector<vector<int>>& visited, vector<vector<vector<int>>> &dp) {\n        if(health <= 0) return false;\n        if(x==m-1 && y == n-1) {\n            if(health >= 1) return true;\n            else return false;\n        }\n        if (dp[x][y][health] != -1) {\n            return dp[x][y][health];\n        }\n        visited[x][y] = 1;\n        int delx[] = {-1, 0, 1, 0};\n        int dely[] = {0, 1, 0, -1};\n        for(int i=0; i<4; i++) {\n            int newx = x+delx[i];\n            int newy = y+dely[i];\n            if(safe(newx, newy, m, n, visited)) {\n                int nh = health;\n                if(grid[newx][newy] == 1) nh--;\n                if(walk(newx, newy, grid, nh, m, n, visited, dp)) \n                    return dp[x][y][health] = true;\n            }\n        }\n        visited[x][y] = 0;\n        return dp[x][y][health] = false;\n    }\npublic:\n    bool findSafeWalk(vector<vector<int>>& grid, int health) {\n        if(grid[0][0] == 1) health--;\n        int m = grid.size(), n=grid[0].size();\n        vector<vector<vector<int>>> dp(m, vector<vector<int>>\n        (n, vector<int>(health + 1, -1)));  \n        vector<vector<int>> visited(m, vector<int> (n, 0));\n        return walk(0, 0, grid, health, m, n, visited, dp);\n    }\n};\n```
['Dynamic Programming', 'Depth-First Search', 'Graph', 'Memoization', 'C++']