LeetCode 题解工作台
穿越网格图的安全路径
给你一个 m x n 的二进制矩形 grid 和一个整数 health 表示你的健康值。 你开始于矩形的左上角 (0, 0) ，你的目标是矩形的右下角 (m - 1, n - 1) 。 你可以在矩形中往上下左右相邻格子移动，但前提是你的健康值始终是 正数 。 对于格子 (i, j) ，如果 grid…
6
题型
5
代码语言
3
相关题
当前训练重点
中等 · 图·搜索
答案摘要
我们定义一个二维数组 ，其中 表示从左上角到达 $(i, j)$ 位置的最小健康值。初始时，我们将 设为 ，并将 $(0, 0)$ 加入队列 中。 随后我们不断取出队列中的元素 $(x, y)$，并尝试向四个方向移动。如果移动到了一个合法的位置 $(nx, ny)$，且从 $(x, y)$ 移动到 $(nx, ny)$ 的健康值消耗更小，那么我们就可以更新 $\textit{dist}[nx…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·搜索 题型思路
题目描述
给你一个 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.lengthn == grid[i].length1 <= m, n <= 502 <= m * n1 <= health <= m + ngrid[i][j]要么是 0 ，要么是 1 。
解题思路
方法一：BFS
我们定义一个二维数组 ，其中 表示从左上角到达 位置的最小健康值。初始时，我们将 设为 ，并将 加入队列 中。
随后我们不断取出队列中的元素 ，并尝试向四个方向移动。如果移动到了一个合法的位置 ，且从 移动到 的健康值消耗更小，那么我们就可以更新 ，并将 加入队列 中。
最终，当队列为空时，我们就可以得到 ，即从左上角到达右下角的最小健康值。如果这个值小于 ，那么我们就可以到达右下角，否则我们无法到达。
时间复杂度 ，空间复杂度 。其中 和 分别是矩形的行数和列数。
class Solution:
def findSafeWalk(self, grid: List[List[int]], health: int) -> bool:
m, n = len(grid), len(grid[0])
dist = [[inf] * n for _ in range(m)]
dist[0][0] = grid[0][0]
q = deque([(0, 0)])
dirs = (-1, 0, 1, 0, -1)
while q:
x, y = q.popleft()
for a, b in pairwise(dirs):
nx, ny = x + a, y + b
if (
0 <= nx < m
and 0 <= ny < n
and dist[nx][ny] > dist[x][y] + grid[nx][ny]
):
dist[nx][ny] = dist[x][y] + grid[nx][ny]
q.append((nx, ny))
return dist[-1][-1] < health
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(m _n) in the worst case, as each cell is visited at most once with the highest health. Space complexity is also O(m_ n) for the BFS queue and health tracking matrix. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate immediately considers BFS with health tracking, not plain DFS.
- question_mark
Candidate optimizes with 01 BFS to handle cells with different costs efficiently.
- question_mark
Candidate handles boundary conditions and health depletion correctly during traversal.
常见陷阱
外企场景- error
Failing to track health properly can lead to incorrect true/false results.
- error
Revisiting cells without comparing remaining health can cause TLE or wrong paths.
- error
Ignoring cells with value 1 as costly can result in paths that falsely appear safe.
进阶变体
外企场景- arrow_right_alt
Change movement to include diagonals and recalculate paths.
- arrow_right_alt
Vary the health decrement for different cells instead of 1 per obstacle.
- arrow_right_alt
Determine the minimum starting health needed to guarantee a safe walk.