3286.穿越网格图的安全路径：“优先”队列

【LetMeFly】3286.穿越网格图的安全路径：“优先”队列

力扣题目链接：https://leetcode.cn/problems/find-a-safe-walk-through-a-grid/

给你一个 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 。

解题方法：优先队列

从起点开始，不论上下左右怎么走，走到为$0$的格子都不掉血，走到为$1$的格子则代价$+1$。

我们可以换个思路，从起点到终点最小的代价是多少？如果最小的代价小于初始健康值则返回true。

因此，可以使用一个优先队列，每次队列中代价最小的位置出队，更新其上下左右相邻格子的到达代价。如果上下左右四个格子到达的代价更小则入队。

优化

由于新入队格子的代价最多是当前格子+1，所以其实队列中最多只有两个值，我们也可以使用双端队列，如果新入队格子代价和现在相等则对到队首，否则入队到队尾。

• 时间复杂度$O(size(grid))$，优先队列优化后无需排序。
• 空间复杂度$O(size(grid))$

AC代码

C++

/*
 * @LastEditTime: 2026-07-14 11:26:09
 */
typedef pair<int, int> pii;
class Solution {
private:
    constexpr static int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public:
    bool findSafeWalk(vector<vector<int>>& grid, int health) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<int>> costs(n, vector<int>(m, 100000000));
        deque<pii> q;
        q.push_back({0, 0});
        costs[0][0] = grid[0][0];  // 注意起点可能直接掉血
        while (q.size()) {
            auto [x, y] = q.front();
            q.pop_front();
            for (auto [dx, dy] : directions) {
                int nx = x + dx, ny = y + dy;
                if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                    int next_cost = costs[x][y] + grid[nx][ny];
                    if (next_cost >= costs[nx][ny]) {
                        continue;
                    }
                    costs[nx][ny] = next_cost;
                    if (grid[nx][ny]) {
                        q.push_back({nx, ny});
                    } else {
                        q.push_front({nx, ny});
                    }
                }
            }
        }
        return costs[n - 1][m - 1] < health;
    }
};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源