problem
TC: O(n*m) , SC :O(n*m) + O(n*m)
int Directions[][] =
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;
}
}
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;
}
Top comments (0)