Q22 Swim in Rising Water - LeetCode 778

 class Solution {
    public int swimInWater(int[][] grid) {
        /* Q22 graph playlist , we apply a modified djikstra algo to find the smallest route
        as smallest route will depend on the maximum time cell of that route , we write 
        compareTo function according to maxvalue

        every pair in PQ stores maximum time cell in that route 
        */
        int m = grid.length , n = grid[0].length;

        Queue<pair> pq = new PriorityQueue<>();
        pq.add(new pair(0 , 0 , grid[0][0] , grid[0][0]));
        boolean visited[][] = new boolean[m][n];

        //applying djikstra according to Max time cell in a route
        while(pq.size() > 0){
            pair rem = pq.remove();
            int x = rem.x , y = rem.y , wt = rem.wt , max = rem.max;

            visited[x][y] = true;

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

            //calling for all edges
            for(int i = 0 ;i < 4 ;i++){
                int rowdash = x + dir[i][0];
                int coldash = y + dir[i][1];
                
                //checking if edge is valid
                if(rowdash >= 0 && rowdash < m &&
                coldash >= 0 && coldash < n && visited[rowdash][coldash] == false  ){
                    
                    //finding new max in the current route and updating the next time cell
                    int newMax = Math.max(max , grid[rowdash][coldash]);
                    pq.add(new pair(rowdash ,coldash , grid[rowdash][coldash],newMax));
                }
                
            }
        }
        return -1;
    }

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

    public class pair implements Comparable<pair>{
        int x , y , wt , max;

        pair(){

        }
        pair(int x , int y , int wt , int max){
            this.x = x;
            this.y = y;
            this.wt = wt;
            this.max = max;     //current max-time in route
        }

        public int compareTo(pair o){
            return this.max - o.max;
        }
    }
}