LC 3286. Find a Safe Walk Through a Grid

https://leetcode.com/problems/find-a-safe-walk-through-a-grid/description/

class Solution {
public:
    int dr[4] = {-1, 1, 0, 0};
    int dc[4] = {0, 0, -1, 1};
    bool findSafeWalk(vector<vector<int>>& grid, int health) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<bool>> vis(m, vector<bool>(n, false));
        priority_queue<pair<int, pair<int, int>>> pq;
        pq.push({health - grid[0][0], {0, 0}});
        while (!pq.empty()) {
            auto [heal, pos] = pq.top();
            pq.pop();
            if (heal == 0) continue;
            auto [x, y] = pos;
            if (x == m - 1 && y == n - 1) return true;
            if (vis[x][y]) continue;
            vis[x][y] = true;
            for (int k = 0; k < 4; k++) {
                int nx = x + dr[k];
                int ny = y + dc[k];
                if (nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
                if (grid[nx][ny] && heal == 1) continue;
                pq.push({heal - grid[nx][ny], {nx, ny}});
            }
        }
        return false;
    }
};

算是很經典的 PQ + BFS 的題目

首先我們需要發現他要使用到 PQ，關鍵的地方在有血量限制，那代表我們到達某個點的時候希望就會是到達該點可能的血量中的最大血量，那就很適合使用 PQ，因為 PQ 只會將當前最大血量的放在最前面，這樣就可以保證只要走到該地方，則當下的血量就是到達該地方的最大血量。