3286. Find a Safe Walk Through a Grid

import java.util.*;

class Solution {
    public boolean findSafeWalk(List<List<Integer>> grid, int health) {
        int m = grid.size(), n = grid.get(0).size();

        int[][] best = new int[m][n];
        for (int[] row : best) Arrays.fill(row, -1);

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[2] - a[2]);

        int startHealth = health - grid.get(0).get(0);
        if (startHealth <= 0) return false;

        best[0][0] = startHealth;
        pq.offer(new int[]{0, 0, startHealth});

        int[][] dir = {{1,0},{-1,0},{0,1},{0,-1}};

        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int x = cur[0], y = cur[1], h = cur[2];

            if (h != best[x][y]) continue;

            if (x == m - 1 && y == n - 1) return true;

            for (int[] d : dir) {
                int nx = x + d[0];
                int ny = y + d[1];

                if (nx < 0 || ny < 0 || nx >= m || ny >= n) continue;

                int nh = h - grid.get(nx).get(ny);

                if (nh > 0 && nh > best[nx][ny]) {
                    best[nx][ny] = nh;
                    pq.offer(new int[]{nx, ny, nh});
                }
            }
        }

        return false;
    }
}

import heapq

class Solution:
    def findSafeWalk(self, grid, health):

        m = len(grid)
        n = len(grid[0])

        best = [[-1] * n for _ in range(m)]

        start = health - grid[0][0]

        if start <= 0:
            return False

        pq = [(-start, 0, 0)]
        best[0][0] = start

        dirs = [(1,0),(-1,0),(0,1),(0,-1)]

        while pq:

            h, x, y = heapq.heappop(pq)
            h = -h

            if h != best[x][y]:
                continue

            if x == m - 1 and y == n - 1:
                return True

            for dx, dy in dirs:

                nx = x + dx
                ny = y + dy

                if 0 <= nx < m and 0 <= ny < n:

                    nh = h - grid[nx][ny]

                    if nh > 0 and nh > best[nx][ny]:
                        best[nx][ny] = nh
                        heapq.heappush(pq, (-nh, nx, ny))

        return False

class Solution {
public:
    bool findSafeWalk(vector<vector<int>>& grid, int health) {

        int m = grid.size();
        int n = grid[0].size();

        vector<vector<int>> best(m, vector<int>(n, -1));

        priority_queue<vector<int>> pq;

        int start = health - grid[0][0];

        if(start <= 0) return false;

        best[0][0] = start;
        pq.push({start,0,0});

        int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};

        while(!pq.empty()){

            auto cur=pq.top();
            pq.pop();

            int h=cur[0];
            int x=cur[1];
            int y=cur[2];

            if(h!=best[x][y]) continue;

            if(x==m-1 && y==n-1)
                return true;

            for(auto &d:dir){

                int nx=x+d[0];
                int ny=y+d[1];

                if(nx<0||ny<0||nx>=m||ny>=n)
                    continue;

                int nh=h-grid[nx][ny];

                if(nh>0 && nh>best[nx][ny]){

                    best[nx][ny]=nh;
                    pq.push({nh,nx,ny});
                }
            }
        }

        return false;
    }
};

var findSafeWalk = function(grid, health) {

    const m = grid.length;
    const n = grid[0].length;

    const best = Array.from({length:m},()=>Array(n).fill(-1));

    const start = health - grid[0][0];

    if(start<=0) return false;

    const pq=[[0,0,start]];

    best[0][0]=start;

    const dir=[[1,0],[-1,0],[0,1],[0,-1]];

    while(pq.length){

        pq.sort((a,b)=>b[2]-a[2]);

        const [x,y,h]=pq.shift();

        if(h!==best[x][y]) continue;

        if(x===m-1 && y===n-1)
            return true;

        for(const [dx,dy] of dir){

            const nx=x+dx;
            const ny=y+dy;

            if(nx<0||ny<0||nx>=m||ny>=n)
                continue;

            const nh=h-grid[nx][ny];

            if(nh>0 && nh>best[nx][ny]){

                best[nx][ny]=nh;
                pq.push([nx,ny,nh]);
            }
        }
    }

    return false;
};