Beats 100%| O(m x n) | DFS Recursion + Memoization + Pruning + Backtracking
Intuition\nThe problem is about navigating through a grid where some cells are unsafe, reducing your health. The goal is to determine if you can traverse from t
# Intuition\nThe problem is about navigating through a grid where some cells are unsafe, reducing your health. The goal is to determine if you can traverse from the top-left corner to the bottom-right corner while keeping your health positive. If your health drops below 1 at any point, you fail the challenge.\n\nTo solve this, we explore all possible paths using Depth-First Search (DFS) and employ pruning to avoid unnecessary computations once a valid path is found.\n\nThe tricky part is to understand that:\n1. You must include the first and the last cell.\n2. If you have already been to a cell with X amount of health before, and you somehow reach it again with Y < X health, there is no point exploring it. This is the key here. \n\n# Approach\n1. **Matrix Conversion:** First, we convert the input `List<List<Integer>>` to a 2D array for easier access and manipulation.\n2. **DFS with Memoization:** Starting from the top-left corner, we use DFS to explore all possible paths. We keep track of visited nodes and memoize the health values to avoid revisiting paths with lower health.\n3. **Health Tracking:** As we move from one cell to another, we update the health by subtracting 1 for unsafe cells. **If the new health is higher than the previous recorded health for a given cell, we continue exploring that path.**\n4. **Pruning:** Once we find a valid path that leads to the bottom-right corner, we can immediately return `true` and stop exploring other branches (pruning). This is crucial to optimize the solution and avoid unnecessary computations.\n5. **Backtracking:** Mark cells as visited during the DFS exploration and unmark them after checking all paths to allow revisiting them from different routes if necessary.\n6. **Success Condition:** The objective is to reach the bottom-right corner with at least 1 health point remaining.\n\n# Complexity\n- **Time complexity:** $$O(m \\times n)$$ because each cell can be visited multiple times due to backtracking and memoization.\n  \n- **Space complexity:** $$O(m \\times n)$$ for storing the visited and memoization matrices.\n\n# Code\n```java\nclass Solution {\n    public boolean findSafeWalk(List<List<Integer>> grid, int health) {\n        int[][] matrix = new int[grid.size()][grid.get(0).size()];\n        boolean[][] visited = new boolean[matrix.length][matrix[0].length];\n        for (int i = 0; i < matrix.length; i++) {\n            for (int j = 0; j < matrix[0].length; j++) {\n                matrix[i][j] = grid.get(i).get(j);\n            }\n        }\n        visited[0][0] = true;\n        int[][] dp = new int[matrix.length][matrix[0].length];\n        health -= matrix[0][0];\n        dp[0][0] = health;\n\n        return helper(matrix, health, 0, 0, visited, dp);\n    }\n\n    private boolean helper(int[][] matrix, int runningHealth, int row, int col, boolean[][] visited, int[][] dp) {\n        if (runningHealth < 1) return false;\n\n        if (row == matrix.length - 1 && col == matrix[0].length - 1) {\n            return runningHealth >= 1;\n        }\n\n        boolean ans = false;\n        \n        // Move Up\n        if (row - 1 >= 0 && !visited[row - 1][col]) {\n            int health = runningHealth - matrix[row - 1][col];\n            if (health > dp[row - 1][col]) {\n                dp[row - 1][col] = health;\n                visited[row - 1][col] = true;\n                ans |= helper(matrix, health, row - 1, col, visited, dp);\n                visited[row - 1][col] = false;\n            }\n        }\n        if (ans) return ans;  // Pruning: If a valid path is found, return immediately to avoid unnecessary exploration\n\n        // Move Down\n        if (row + 1 < matrix.length && !visited[row + 1][col]) {\n            int health = runningHealth - matrix[row + 1][col];\n            if (health > dp[row + 1][col]) {\n                dp[row + 1][col] = health;\n                visited[row + 1][col] = true;\n                ans |= helper(matrix, health, row + 1, col, visited, dp);\n                visited[row + 1][col] = false;\n            }\n        }\n        if (ans) return ans;  // Pruning: Return early if we found a valid path\n\n        // Move Left\n        if (col - 1 >= 0 && !visited[row][col - 1]) {\n            int health = runningHealth - matrix[row][col - 1];\n            if (health > dp[row][col - 1]) {\n                dp[row][col - 1] = health;\n                visited[row][col - 1] = true;\n                ans |= helper(matrix, health, row, col - 1, visited, dp);\n                visited[row][col - 1] = false;\n            }\n        }\n        if (ans) return ans;  // Pruning: Stop exploring further if a solution is found\n\n        // Move Right\n        if (col + 1 < matrix[0].length && !visited[row][col + 1]) {\n            int health = runningHealth - matrix[row][col + 1];\n            if (health > dp[row][col + 1]) {\n                dp[row][col + 1] = health;\n                visited[row][col + 1] = true;\n                ans |= helper(matrix, health, row, col + 1, visited, dp);\n                visited[row][col + 1] = false;\n            }\n        }\n        return ans;\n    }\n}\n
['Dynamic Programming', 'Backtracking', 'Depth-First Search', 'Memoization', 'Matrix', 'Java']