目标
给你一个 m x n 的二进制矩形 grid 和一个整数 health 表示你的健康值。
你开始于矩形的左上角 (0, 0) ，你的目标是矩形的右下角 (m - 1, n - 1) 。
你可以在矩形中往上下左右相邻格子移动，但前提是你的健康值始终是 正数 。
对于格子 (i, j) ，如果 grid[i][j] = 1 ，那么这个格子视为 不安全 的，会使你的健康值减少 1 。
如果你可以到达最终的格子，请你返回 true ，否则返回 false 。
注意 ，当你在最终格子的时候，你的健康值也必须为 正数 。
示例 1：
输入：grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]], health = 1
输出：true
解释：
沿着图中灰色格子走，可以安全到达最终的格子。示例 2：
输入：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
输出：false
解释：
健康值最少为 4 才能安全到达最后的格子。示例 3：
输入：grid = [[1,1,1],[1,0,1],[1,1,1]], health = 5
输出：true
解释：
沿着下图中灰色格子走，可以安全到达最终的格子。
任何不经过格子 (1, 1) 的路径都是不安全的，因为你的健康值到达最终格子时，都会小于等于 0 。说明：
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 50
- 2 <= m * n
- 1 <= health <= m + n
- grid[i][j] 要么是 0 ，要么是 1 。
思路
有一个 m x n 的二进制矩阵，从左上角 (0, 0) 出发，可以沿上下左右四个方向移动到相邻的格子。如果经过的格子值为 1 视为不安全，健康度 health 减 1。判断是否存在路径使得到达 (m - 1, n - 1) 时，health > 0。
判断路径和是否严格小于 health，可以使用 Dijkstra 求出最短路。
代码
/**
* @date 2026-07-02 9:09
*/
public class FindSafeWalk3286 {
private final int[][] directions = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public boolean findSafeWalk(List<List<Integer>> grid, int health) {
int m = grid.size();
int n = grid.get(0).size();
int[][] dis = new int[m][n];
for (int[] row : dis) {
Arrays.fill(row, Integer.MAX_VALUE);
}
// 出错点：不要忘了初始化
dis[0][0] = grid.get(0).get(0);
Deque<int[]> q = new ArrayDeque<>();
q.offer(new int[]{0, 0});
while (!q.isEmpty()) {
int[] p = q.poll();
int r = p[0], c = p[1];
for (int[] d : directions) {
int nr = r + d[0];
int nc = c + d[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && dis[r][c] + grid.get(nr).get(nc) < dis[nr][nc]) {
Integer cost = grid.get(nr).get(nc);
dis[nr][nc] = dis[r][c] + cost;
if (cost == 0) {
q.offerFirst(new int[]{nr, nc});
} else {
q.offer(new int[]{nr, nc});
}
}
}
}
return dis[m - 1][n - 1] < health;
}
}
性能
