🗒️3286. 穿越网格图的安全路径
2025-3-17
| 2025-3-17
0  |  阅读时长 0 分钟
type
status
date
slug
summary
tags
category
icon
password
创建时间
Mar 17, 2025 05:37 AM
给你一个 m x n 的二进制矩形 grid 和一个整数 health 表示你的健康值。
你开始于矩形的左上角 (0, 0) ,你的目标是矩形的右下角 (m - 1, n - 1) 。
你可以在矩形中往上下左右相邻格子移动,但前提是你的健康值始终是 正数 。
对于格子 (i, j) ,如果 grid[i][j] = 1 ,那么这个格子视为 不安全 的,会使你的健康值减少 1 。
如果你可以到达最终的格子,请你返回 true ,否则返回 false 。
注意 ,当你在最终格子的时候,你的健康值也必须为 正数 。

BFS

BFS 解决 0-1 边权问题使用双端队列解决。
下面的写法不对
0-1 BFS 本质是对 Dijkstra 算法的优化。因为边权只有 0 和 1,我们可以把最小堆换成双端队列,遇到 0 边权就加入队首,遇到 1 边权就加入队尾,这样可以保证队首总是最小的,就不需要最小堆了。——灵茶山艾府

📎 参考

  • 【题单】滑动窗口与双指针
  • 【题单】网格图(DFS/BFS/综合应用)
  • 决策树1824. 最少侧跳次数
    Loading...