Swim in Rising Water

shriyanshi24jindal

Mar 30th, 2026

129

Never

Not a member of GistPad yet? Sign Up, it unlocks many cool features!

Java 15.53 KB | None | 0 0

copy raw download clone embed print report

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];
}
}

RAW Paste Data Copied

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];
    }
}