DEV Community

Prashant Mishra
Prashant Mishra

Posted on

Find safest walk through the grid

problem
TC: O(n*m) , SC :O(n*m) + O(n*m)
int Directions[][] = {{0,1},{0,1},{1,0},{1,0}};\{\{0,-1\},\{0,1\},\{-1,0\},\{1,0\}\}; i.e left,right,up and down
BFS approach:


class Triple{
    int i;
    int j ;
    int h;
    public Triple(int i, int j, int h){
        this.i =i;
        this.j = j;
        this.h  =h;
    }
}
class Solution {
    public boolean findSafeWalk(List<List<Integer>> grid, int health) {
        int visited[][] = new int[grid.size()][grid.get(0).size()];

        Queue<Triple> q = new PriorityQueue<>((a,b)->b.h-a.h);
        q.add(new Triple(0,0,health-grid.get(0).get(0)));

        while(!q.isEmpty()){
            Triple t = q.remove();
            if(t.i ==grid.size()-1 && t.j  == grid.get(0).size()-1) return true;
            if(visited[t.i][t.j]==1) continue;
            visited[t.i][t.j] = 1;
            int dirs[][]  = Directions; 
            for(int dir[] : dirs){
                int x = t.i+dir[0];
                int y = t.j+dir[1];
                if(x>=0 && y>=0 && x<grid.size() && y<grid.get(0).size() && visited[x][y]==0  && t.h-grid.get(x).get(y)>0){
                    q.add(new Triple(x,y,t.h-grid.get(x).get(y)));
                }
            }

        }
        return false;
    }
} 
Enter fullscreen mode Exit fullscreen mode

DFS approach: leading to TLE
Just use below method call in the above findSafeWalk();

    public boolean possible(int i, int j, List<List<Integer>> grid,int health,int visited[][]){
        if(i ==grid.size()-1 && j == grid.get(0).size()-1 && health>0) return true;
        if(visited[i][j]==1) return false;

        //base case
        visited[i][j] = 1;
        int dirs[][]  = Directions;
        for(int dir[] : dirs){
            int x = i+dir[0];
            int y = j+dir[1];
            if(x>=0 && y>=0 && x<grid.size() && y<grid.get(0).size() && visited[x][y]==0  && health>0){
                visited[x][y] = 1;
                if(possible(x,y,grid,health-grid.get(x).get(y),visited)) return true;
                visited[x][y] = 0;
            }
        }
        visited[i][j] = 0;
        return false;


    }
Enter fullscreen mode Exit fullscreen mode

Top comments (0)