Solution | JavaScript | C++ | Python
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```javascript []\nvar findSafeWalk = function(grid, health) {\n    let yMax = grid.length; xMax = grid[0].length;\n\n    // memoization\n    let dp = new Array(yMax).fill().map(() => new Array(xMax).fill().map(() => new Array(health+1).fill(null)));\n\n    let journey = (y, x, health, visited) => {\n        // boundary check\n        if(x<0 || x>=xMax || y<0 || y>=yMax) return false;\n\n        // check if it is visited \n        if(visited[y][x]) return false;\n\n        // enough health\n        if(health < 1) return false;\n\n        if(dp[y][x][health] != null) return dp[y][x][health];\n\n        // if the grid block is 1, decrement the health by 1 \n        if(grid[y][x] == 1) health -= 1;\n        visited[y][x] = true;\n\n        // check if it is the bottom-right corner\n        if(y === yMax-1 && x === xMax-1 && health >= 1) return true;\n\n        let foundPath = journey(y, x-1, health, visited) ||\n                        journey(y-1, x, health, visited) ||\n                        journey(y, x+1, health, visited) ||\n                        journey(y+1, x, health, visited);\n\n        // once the visit finished undo visited and health \n        visited[y][x] = false;\n        if(grid[y][x] == 1) health += 1;\n\n        // store the value to memoization\n        dp[y][x][health] = foundPath;\n        return dp[y][x][health];\n    };\n\n    // records visits\n    let visited = new Array(yMax).fill().map(() => new Array(xMax).fill(false));\n\n    return journey(0, 0, health, visited);\n};\n```\n``` cpp []\nclass Solution {\npublic:\n    \n    bool journey(int y, int x, int& health, vector<vector<bool>>& visited, vector<vector<int>>& grid, vector<vector<vector<int>>>& dp) {\n\n        // check boundary\n        if(y < 0 || y >= visited.size() || x < 0 || x >= visited[0].size()) return false;\n\n        // check if it is visited\n        if(visited[y][x]) return false;\n\n        // health\n        if(health <= 0) return false;\n\n        // check if this is in memoization\n        if(dp[y][x][health] != -1) return dp[y][x][health];\n\n        // if the grid block is 1, decrement the health by 1 \n        if(grid[y][x] == 1) health--;\n\n\n        // check if it is the bottom-right corner\n        if(y == visited.size()-1 && x == visited[0].size()-1 && health >= 1) return true;\n        visited[y][x] = true;\n\n        bool foundPath = journey(y, x-1, health, visited, grid, dp) ||\n                         journey(y-1, x, health, visited, grid, dp) || \n                         journey(y, x+1, health, visited, grid, dp) || \n                         journey(y+1, x, health, visited, grid, dp);   \n\n        // once the visit finished undo visited and health \n        visited[y][x] = false;\n        if(grid[y][x] == 1) health++;\n        \n        // store the value to memoization\n        if(foundPath) dp[y][x][health] = 1;\n        else dp[y][x][health] = 0;\n        return dp[y][x][health];\n\n    };\n    bool findSafeWalk(vector<vector<int>>& grid, int health) {\n        int yMax = grid.size(), xMax = grid[0].size();\n        \n        // memoization\n        vector<vector<vector<int>>> dp(yMax, vector<vector<int>>(xMax, vector<int>(health+1, -1)));\n\n        // records visits\n        vector<vector<bool>> visited(yMax, vector<bool>(xMax, false));\n        \n        return journey(0, 0, health, visited, grid, dp);\n    }\n};\n```\n``` python []\nclass Solution:\n    def findSafeWalk(self, grid: List[List[int]], health: int) -> bool:\n        yMax, xMax = len(grid), len(grid[0])\n        \n        # memoization\n        dp = [[[None for _ in range(health+1)] for _ in range(xMax)] for _ in range(yMax)]\n\n        def journey(y, x, health, visited):\n            \n            # boundary check\n            if y < 0 or y >= yMax or x < 0 or x >= xMax: return False\n\n            # health\n            if health <= 0: return False\n\n            # check if it is visited\n            if visited[y][x]: return False\n\n            # memoization check\n            if dp[y][x][health] != None: return dp[y][x][health]\n\n            if grid[y][x] == 1: health -= 1\n            visited[y][x] = True\n            \n            if y == yMax-1 and x == xMax-1 and health >= 1: return True\n\n            foundPath=journey(y, x-1, health, visited) or journey(y-1, x, health, visited) or journey(y, x+1, health, visited) or journey(y+1, x, health, visited)\n\n            if grid[y][x] == 1: health += 1\n            visited[y][x] = False\n\n            # store the result to memoization\n            dp[y][x][health] = foundPath\n            return dp[y][x][health]\n            \n\n        visited = [[False for _ in range(xMax)] for _ in range(yMax)]\n        return journey(0, 0, health, visited)\n```
['Breadth-First Search', 'C++', 'Python3', 'JavaScript']