dfs + memo + backtracking
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem requires finding a safe path through a binary grid where unsafe cells decre
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem requires finding a safe path through a binary grid where unsafe cells decrease your health. You must move from the top-left corner to the bottom-right corner while maintaining a health value greater than or equal to 1. Unsafe cells (marked as 1) reduce health by 1, so the goal is to navigate through the grid while minimizing health loss.\n\nThe idea is to use DFS or BFS to explore different paths and track the remaining health. If at any point the health falls below 1, that path is abandoned. The challenge lies in finding a path where your health remains positive when reaching the destination.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nDFS  Traversal: Start from the top-left corner and explore all four possible directions (up, down, left, right) using a depth-first search (DFS)\n\nHealth Management:\n\n* For every move, check if the next cell is unsafe (grid[i][j] == 1).  If it is, reduce the current health by 1.\n* If health drops below 1, terminate that path exploration.\n\nVisited Matrix:\n\n* To avoid revisiting already checked cells with insufficient health, maintain a 2D array vis[x][y] that keeps track of the minimum health required to reach a cell (x, y). This ensures that if you revisit the same cell but with lower health, you skip further exploration.\n\nEnd Condition:\n\n* When the traversal reaches the bottom-right corner with health >= 1, return True.\n* If no valid path is found that maintains a positive health value, return False.\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n* * O(m * n), where m is the number of rows and n is the number of columns in the grid. In the worst case, every cell in the grid is explored.\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n* * O(m * n), due to the space used by the vis matrix and recursion (for DFS)\n\n# Code\n```python3 []\nclass Solution:\n    def findSafeWalk(self, grid: List[List[int]], h: int) -> bool:\n        m = len(grid)\n        n = len(grid[0])\n        vis = [[0 for _ in range(n)] for _ in range(m)]\n        memo = {}\n        def dfs(x,y,ans):\n            if x<0 or x>=m or y>=n or y<0 or vis[x][y]==1 or ans>=h:\n                return float(\'inf\')\n            if x==m-1 and y==n-1:\n                return ans+grid[x][y]\n            if (x,y,ans) in memo:\n                return memo[(x,y,ans)]\n            vis[x][y] = 1\n            memo[(x,y,ans)] = min(dfs(x+1,y,ans+grid[x][y]),dfs(x-1,y,ans+grid[x][y]),dfs(x,y+1,ans+grid[x][y]),dfs(x,y-1,ans+grid[x][y]))\n            vis[x][y] = 0\n            return memo[(x,y,ans)]\n        a = dfs(0,0,0)\n        return a-h<0\n```
['Backtracking', 'Depth-First Search', 'Memoization', 'Python3']