Python3 || dfs  ||
\npython3 []\nclass Solution:\n    def findSafeWalk(self, grid: List[List[int]], health: int) -> bool:\n\n        @lru_cache(None)\n        def dp(x: int, y: in
\n```python3 []\nclass Solution:\n    def findSafeWalk(self, grid: List[List[int]], health: int) -> bool:\n\n        @lru_cache(None)\n        def dp(x: int, y: int, health_used: int)-> int: \n\n            if health_used == health or (x, y) not in eligible: return inf\n\n            cnt = health_used + grid[x][y]\n            if (x, y) == (m - 1 , n - 1): return cnt\n            \n            eligible.discard((x, y))\n\n            res = min(dp(x + 1, y, cnt), dp(x, y + 1, cnt),\n                      dp(x - 1, y, cnt), dp(x, y - 1, cnt))\n\n            eligible.add((x, y))\n\n            return res\n\n\n        m, n = len(grid), len(grid[0])\n        eligible = set(product(range(m), range(n)))\n\n        return dp(0,0,0) < health        \n        \n```\n[https://leetcode.com/problems/find-a-safe-walk-through-a-grid/submissions/1390177636/](https://leetcode.com/problems/find-a-safe-walk-through-a-grid/submissions/1390177636/)\n\nI could be wrong, but I think that time complexity is *O*(*MNH*) and space complexity is *O*(*MNH*), in which *M, N, H* ~ `m`, `n`, `health`.
['Python3']