class Pair
{
    int row;
    int col;
    int dist;
    Pair(int dist, int row, int col)
    {
        this.dist = dist;
        this.row = row;
        this.col = col;
    }
}
 
class Solution {
    // IDEA: Dijkstra alogrithm, instead of storeing distance as 0 for source vertex, store the water elevation
    public int swimInWater(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
 
        int[] source = new int[]{0,0};
        int[] destination = new int[]{n-1,m-1};
 
        // same starting and ending position
        if(source[0] == destination[0] && source[1] == destination[1])
            return 0;
 
        // Step-1 Create a distance matrix
        int[][] distance = new int[n][m];
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                distance[i][j]=Integer.MAX_VALUE;
            }
        }
        // Starting point elevation matters!
        distance[source[0]][source[1]] = grid[0][0]; 
 
        // Step-2 Store the nodes into MIN-HEAP accoriding to node's distances
        PriorityQueue<Pair> pq = new PriorityQueue<>( (x,y) -> Integer.compare(x.dist, y.dist));
        // Starting point elevation matters!
        pq.add(new Pair(grid[0][0], source[0], source[1]));
 
 
        int[] deltaRow = {-1, 0, 1, 0};
        int[] deltaCol = {0, 1, 0, -1};
 
        int maxNode = 0;
        while(!pq.isEmpty())
        {
            Pair pair = pq.poll();
            int row = pair.row;
            int col = pair.col;
            int currentDist = pair.dist;
 
            for(int i=0; i<4; i++)
            {
                int nRow = row + deltaRow[i];
                int nCol = col + deltaCol[i];
 
                if(nRow >= 0 && nRow < n && nCol>=0 && nCol < m)
                {
                    // In the “Swim in Rising Water”, the cost to enter a cell is the elevation of the cell.
                    int nextDist = Math.max(currentDist, grid[nRow][nCol]);
 
                    // checking if new distance is less than the current distance stored
                    // if yes then update it and add pair to queue
                    if(distance[nRow][nCol] > nextDist) 
                    {
                        distance[nRow][nCol] = nextDist;
                        pq.add(new Pair(nextDist, nRow, nCol));
                    }
                }
            }
        }
        return distance[n-1][m-1];
    }
}