Easy to understand and Easy Approach 😊😊
Intuition
We are performing a Depth-First Search (DFS) with pruning using memoization.
The grid is used as a graph, where adjacent cells represent edges.
If a p
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
* We are performing a Depth-First Search (DFS) with pruning using memoization.
* The grid is used as a graph, where adjacent cells represent edges.
* If a path exists to the destination without exhausting health, return true; otherwise, return false.
* The solution optimally avoids recalculating paths that have already been explored by storing results in dp[i][j][health].


# Approach
<!-- Describe your approach to solving the problem. -->
1. Recursive Backtracking with Memoization

* The function checking(grid, i, j, health, dp) explores possible paths recursively.
* Memoization (dp[i][j][health]) is used to store results for previously visited states to avoid redundant computations.
2. Base Cases

* If the cell (i, j) contains 1, health is decreased by 1.
* If health becomes 0 or goes negative, the path is not possible.
* If (i, j) is out of bounds, return false.
* If (i, j) is the destination (m-1, n-1), return true.
3. Exploring Four Possible Moves (Up, Down, Left, Right)

* Mark the current cell as visited (-1) to avoid cycles.
* Recursively explore all four directions (up, down, left, right).
* If any path leads to the destination, return true.
* Restore the grid after backtracking to allow other recursive paths.
4. Memoization (dp[i][j][health])

* To prevent redundant calculations, store the result for each (i, j, health) state.
* If a state is already computed, return the stored result.

# Complexity
- Time complexity: O(m * n * health)
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: O(m * n * health)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```java []
class Solution {
    public boolean findSafeWalk(List<List<Integer>> grid, int health) {
        Boolean[][][] dp = new Boolean[grid.size()+1][grid.get(0).size()+1][health+1];
        return checking(grid, 0, 0, health, dp);
    }
    public boolean checking(List<List<Integer>> grid, int i, int j, int health, Boolean[][][] dp){
        if(grid.get(i).get(j) == 1){
            health -= 1;
        }
        if(health < 1 || i < 0 || i >= grid.size() || j < 0 || j >= grid.get(0).size()){
            return false;
        }
        if(i == grid.size()-1 && j == grid.get(0).size()-1){
            return true;
        }
        if(dp[i][j][health] != null){
            return dp[i][j][health];
        }
        boolean ans = false;
        int val = grid.get(i).get(j);
        grid.get(i).set(j, -1);
        if(i-1 >= 0 && grid.get(i-1).get(j) != -1){
            ans |= checking(grid, i-1, j, health, dp);
        }
        if(i+1 < grid.size() && grid.get(i+1).get(j) != -1){
            ans |= checking(grid, i+1, j, health, dp);
        }
        if(j-1 >= 0 && grid.get(i).get(j-1) != -1){
            ans |= checking(grid, i, j-1, health, dp);
        }
        if(j+1 < grid.get(0).size() && grid.get(i).get(j+1) != -1){
            ans |= checking(grid, i, j+1, health, dp);
        }
        grid.get(i).set(j, val);
        return dp[i][j][health] = ans;
    }
}
```
['Array', 'Dynamic Programming', 'Breadth-First Search', 'Matrix', 'Shortest Path', 'Java']