Q2. Find a Safe Walk Through a Grid
You are given an m x n binary matrix grid and an integer health.
You start on the upper-left corner (0, 0) and would like to get to the lower-right corner (m - 1, n - 1).
You can move up, down, left, or right from one cell to another adjacent cell as long as your health remains positive.
Cells (i, j) with grid[i][j] = 1 are considered unsafe and reduce your health by 1.
Return true if you can reach the final cell with a health value of 1 or more, and false otherwise.
Example 1:
Input: grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]], health = 1
Output: true
Explanation:
The final cell can be reached safely by walking along the gray cells below.
Example 2:
Input: grid = [[0,1,1,0,0,0],[1,0,1,0,0,0],[0,1,1,1,0,1],[0,0,1,0,1,0]], health = 3
Output: false
Explanation:
A minimum of 4 health points is needed to reach the final cell safely.
Example 3:
Input: grid = [[1,1,1],[1,0,1],[1,1,1]], health = 5
Output: true
Explanation:
The final cell can be reached safely by walking along the gray cells below.
Any path that does not go through the cell (1, 1) is unsafe since your health will drop to 0 when reaching the final cell.
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 502 <= m * n1 <= health <= m + ngrid[i][j]is either 0 or 1.
class Solution {
private static int[][] visited;
public boolean findSafeWalk(List<List<Integer>> grid, int health) {
visited = new int[grid.size()][grid.get(0).size()];
return helper(grid, health, 0, 0);
}
private boolean helper(List<List<Integer>> grid, int health, int x, int y){
if (x < 0 || x == grid.size() || y < 0 || y == grid.get(0).size() || health <= 0 || visited[x][y] == 1){
return false;
}
if (grid.get(x).get(y) == 1){
health = health - 1;
if (health == 0){
return false;
}
}
if (x == grid.size() - 1 && y == grid.get(0).size() - 1){
return true;
}
visited[x][y] = 1;
// 4 directionss
// if (grid.get(x).get(y) == 1){
// health = health - 1;
// if (health == 0){
// return false;
// }
// }
boolean up = helper(grid, health, x + 1, y);
boolean down = helper(grid, health, x - 1, y);
boolean left = helper(grid, health, x, y + 1);
boolean right = helper(grid, health, x, y - 1);
visited[x][y] = 0;
return (up || down || left || right) ;
}
}
Time Limit Exceeded
The time consumption in your recursive depth-first search (DFS) implementation primarily comes from the following factors:
- Redundant Visits: The algorithm revisits cells that it has already explored without considering whether the revisit offers a better (or worse) outcome in terms of health. Since it marks cells as visited and later unmarks them (
visited[x][y] = 1and thenvisited[x][y] = 0), it effectively explores the same paths multiple times, leading to a high number of recursive calls.- Excessive Recursive Calls: The DFS explores all four possible directions (
up,down,left,right) from each cell, including those that lead back to previously visited cells. Without careful tracking, this results in a lot of redundant paths being checked multiple times, which increases the time complexity significantly.- Health Management: The check and update of health values during recursive calls are crucial, especially when the health goes down to zero. If the condition
health <= 0isn't properly handled or optimized, it leads to unnecessary continuation of recursion even when the path is no longer viable.Optimization Suggestions:
To optimize the code and reduce time consumption, you can implement the following changes:
- Use a Better Condition for Revisits: Instead of simply marking cells as visited (
visited[x][y] = 1), keep track of the maximum health level at which you have visited each cell. Only proceed with the recursion if the current health is greater than any previously recorded health at that cell. This can help prevent revisiting paths with lower health values and reduce unnecessary recursive calls.- Avoid Immediate Reversals: Ensure that when moving in one direction, the recursive call does not immediately move back in the opposite direction unless absolutely necessary. This can be controlled by marking cells temporarily as visited in a way that considers the current path's context (e.g., temporarily increasing health requirements).
- Pruning: Implement pruning strategies where, if you have already determined a path that successfully reaches the goal with valid health, you can immediately terminate further exploration in that branch.
class Solution {
private static int[][] visited;
private static int m;
private static int n;
public boolean findSafeWalk(List<List<Integer>> grid, int health) {
m = grid.size();
n = grid.get(0).size();
visited = new int[m][n];
return helper(grid, health, 0, 0);
}
private boolean helper(List<List<Integer>> grid, int health, int x, int y){
if (x < 0 || x == m|| y < 0 || y == n || health <= 0){
return false;
}
if (grid.get(x).get(y) == 1){
health = health - 1;
if (health == 0){
return false;
}
}
if (x == m - 1 && y == n - 1){
return true;
}
if (visited[x][y] >= health) {
return false;
}
// Update the visited health level at the current cell
visited[x][y] = health;
// 4 directionss
// if (grid.get(x).get(y) == 1){
// health = health - 1;
// if (health == 0){
// return false;
// }
// }
boolean up = helper(grid, health, x + 1, y);
boolean down = helper(grid, health, x - 1, y);
boolean left = helper(grid, health, x, y + 1);
boolean right = helper(grid, health, x, y - 1);
// visited[x][y] = 0;
return (up || down || left || right) ;
}
}