DEV Community

Prashant Mishra
Prashant Mishra

Posted on

Path with minimum effort

Problem

class Solution {
    public int minimumEffortPath(int[][] heights) {
        Queue<Data> q = new PriorityQueue<>((a,b)-> Integer.compare(a.d, b.d));
        q.add(new Data(0,0,0));
        int n = heights.length;
        int m = heights[0].length;
        int min  =Integer.MAX_VALUE;
        int dirs[][] = {{0,-1},{0,1},{-1,0},{1,0}};
        int visited[][] = new int[n][m];
        for(int v[] : visited){
            Arrays.fill(v, (int)1e9);
        }
        visited[0][0] = 0;
        while(!q.isEmpty()){
            Data d = q.remove();
            for(int dir[]: dirs){
                int i = d.i + dir[0];
                int j = d.j + dir[1];
                if(i>=0 && j>=0 && i<n && j<m){
                    int maxEffort = Math.max(d.d, Math.abs(heights[i][j] - heights[d.i][d.j]));
                    if(visited[i][j] > maxEffort){
                        visited[i][j] = maxEffort;
                        q.add(new Data(i,j,maxEffort));
                    }
                }
            }  
        }
        return visited[n-1][m-1] == (int)1e9 ? 0: visited[n-1][m-1];
    }
}
class Data{
    int i;
    int j;
    int d;
    public Data(int i ,int j,int d){
        this.i = i;
        this.j = j;
        this.d =d;
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)