Safest Walk through the grid



This content originally appeared on DEV Community and was authored by Prashant Mishra

Problem

class Solution {
    public boolean findSafeWalk(List<List<Integer>> grid, int health) {
        Queue<Data> q  = new PriorityQueue<>((a,b)-> Integer.compare(b.h,a.h));
        q.add(new Data(0,0,health-grid.get(0).get(0)));
        int m = grid.size();
        int n = grid.get(0).size();
        int dirs[][] = {{0,-1},{0,1},{-1,0},{1,0}};
        int visited[][] = new int[m][n];
        while(!q.isEmpty()){
            Data d = q.remove();
            if(d.i ==m-1 && d.j == n-1) return true;
            for(int dir[] : dirs){
                int i = d.i + dir[0];
                int j = d.j + dir[1];
                if(i>=0 && j>=0 && i< m && j<n && visited[i][j] ==0 && d.h - grid.get(i).get(j) >0){
                    visited[i][j]  = 1;
                    int h = d.h - grid.get(i).get(j);
                    q.add(new Data(i,j,h));
                }
            }
        return false;
    }
class Data{
    int i;
    int j;
    int h;
    public Data(int i, int j, int h){
        this.i = i;
        this.j = j;
        this.h = h;
    }
}


This content originally appeared on DEV Community and was authored by Prashant Mishra