Clean and straight forward | C++ | Java | Depth First Search | Dynamic Programming | Memoization
Time complexity : O(grid.size() * grid[0].size() * health)\n\n### Space complexity : O(grid.size() * grid[0].size() * health)\n\n# Code\njava []\nimport java.ut
### Time complexity : O(grid.size() * grid[0].size() * health)\n\n### Space complexity : O(grid.size() * grid[0].size() * health)\n\n# Code\n```java []\nimport java.util.*;\n\nclass Solution {\n    private boolean f(int row, int col, int health, List<List<Integer>> grid, boolean[][] visited, int[][][] dp) {\n        if(row == grid.size() - 1 && col == grid.get(0).size() - 1 && health > 0) {\n            return grid.get(row).get(col) == 1 && health == 1 ? false : true;\n        }\n        if(health <= 0 || row < 0 || col < 0 || row >= grid.size() || col >= grid.get(0).size()) {\n            return false;\n        }\n        if(visited[row][col] == true) {\n            return false;\n        }\n        if(dp[row][col][health] != -1) {\n            return dp[row][col][health] == 1;\n        }\n        visited[row][col] = true;\n        boolean up = this.f(row - 1, col, health - grid.get(row).get(col), grid, visited, dp);\n        boolean down = this.f(row + 1, col, health - grid.get(row).get(col), grid, visited, dp);\n        boolean left = this.f(row, col - 1, health - grid.get(row).get(col), grid, visited, dp);\n        boolean right = this.f(row, col + 1, health - grid.get(row).get(col), grid, visited, dp);\n        visited[row][col] = false;\n        boolean result = up || down || left || right;\n        dp[row][col][health] = (result == true ? 1 : 0);\n        return result;\n    }\n    public boolean findSafeWalk(List<List<Integer>> grid, int health) {\n        boolean[][] visited = new boolean[grid.size()][grid.get(0).size()];\n        for(boolean[] arr: visited) {\n            Arrays.fill(arr, false);\n        }\n        int[][][] dp = new int[grid.size()][grid.get(0).size()][health + 1];\n        for(int[][] arr1: dp) {\n            for(int[] arr2: arr1) {\n                Arrays.fill(arr2, -1);\n            }\n        }\n        return this.f(0, 0, health, grid, visited, dp);\n    }\n}\n```\n\n```C++ []\nclass Solution {\n    bool f(int row, int col, int health, vector<vector<int>>& grid, vector<vector<bool>>& visited, vector<vector<vector<int>>>& dp) {\n        if(row == grid.size() - 1 and col == grid[0].size() - 1 and health > 0) {\n            return grid[row][col] == 1 and health == 1 ? false : true;\n        }\n        if(health <= 0 or row < 0 or col < 0 or row >= grid.size() or col >= grid[0].size()) {\n            return false;\n        }\n        if(visited[row][col] == true) {\n            return false;\n        }\n        if(dp[row][col][health] != -1) {\n            return dp[row][col][health];\n        }\n        visited[row][col] = true;\n        bool up = this->f(row - 1, col, health - grid[row][col], grid, visited, dp);\n        bool down = this->f(row + 1, col, health - grid[row][col], grid, visited, dp);\n        bool left = this->f(row, col - 1, health - grid[row][col], grid, visited, dp);\n        bool right = this->f(row, col + 1, health - grid[row][col], grid, visited, dp);\n        visited[row][col] = false;\n        return dp[row][col][health] = up or down or left or right;\n    }\n    public:\n    bool findSafeWalk(vector<vector<int>>& grid, int health) {\n        vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), false));\n        vector<vector<vector<int>>> dp(grid.size(), vector<vector<int>>(grid[0].size(), vector<int>(health + 1, -1)));\n        return this->f(0, 0, health, grid, visited, dp);\n    }\n};\n```\n\nHappy Coding !!!
['Dynamic Programming', 'Depth-First Search', 'Memoization', 'C++', 'Java']