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; } } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter