Swim in Rising Water — Dijkstra / Binary Search + BFS

Problem (LeetCode 778)

Grid where grid[r][c] = the time when that cell becomes passable. Find minimum time T to reach bottom-right from top-left.

Solution 1 — Dijkstra (min-heap on elevation)

import heapq

def swimInWater(grid):
    n = len(grid)
    heap = [(grid[0][0], 0, 0)]
    visited = set()
    while heap:
        t, r, c = heapq.heappop(heap)
        if (r,c) in visited: continue
        visited.add((r,c))
        if r == n-1 and c == n-1: return t
        for dr,dc in [(-1,0),(1,0),(0,-1),(0,1)]:
            nr,nc = r+dr,c+dc
            if 0<=nr<n and 0<=nc<n and (nr,nc) not in visited:
                heapq.heappush(heap, (max(t, grid[nr][nc]), nr, nc))
    return -1

Solution 2 — Binary Search + BFS

from collections import deque

def swimInWater(grid):
    n = len(grid)

    def can_reach(T):
        if grid[0][0] > T: return False
        q = deque([(0,0)])
        vis = {(0,0)}
        while q:
            r,c = q.popleft()
            if r==n-1 and c==n-1: return True
            for dr,dc in [(-1,0),(1,0),(0,-1),(0,1)]:
                nr,nc = r+dr,c+dc
                if 0<=nr<n and 0<=nc<n and (nr,nc) not in vis and grid[nr][nc]<=T:
                    vis.add((nr,nc))
                    q.append((nr,nc))
        return False

    lo,hi = grid[0][0], n*n-1
    while lo < hi:
        mid = (lo+hi)//2
        if can_reach(mid): hi = mid
        else: lo = mid+1
    return lo

JavaScript

function swimInWater(grid) {
    const n=grid.length, vis=new Set();
    const heap=[[grid[0][0],0,0]];
    const pop=()=>{let mi=0;for(let i=1;i<heap.length;i++)if(heap[i][0]<heap[mi][0])mi=i;return heap.splice(mi,1)[0];};
    while(heap.length){const[t,r,c]=pop();const k=r+','+c;if(vis.has(k))continue;vis.add(k);if(r===n-1&&c===n-1)return t;
        for(const[dr,dc]of[[-1,0],[1,0],[0,-1],[0,1]]){const[nr,nc]=[r+dr,c+dc];if(nr>=0&&nr<n&&nc>=0&&nc<n&&!vis.has(nr+','+nc))heap.push([Math.max(t,grid[nr][nc]),nr,nc]);}}
    return -1;
}

Java

import java.util.*;
public int swimInWater(int[][] g) {
    int n=g.length; boolean[][]vis=new boolean[n][n];
    PriorityQueue<int[]>pq=new PriorityQueue<>(Comparator.comparingInt(a->a[0]));
    pq.offer(new int[]{g[0][0],0,0}); int[][]d={{-1,0},{1,0},{0,-1},{0,1}};
    while(!pq.isEmpty()){int[]top=pq.poll();int t=top[0],r=top[1],c=top[2];if(vis[r][c])continue;vis[r][c]=true;if(r==n-1&&c==n-1)return t;for(int[]dr:d){int nr=r+dr[0],nc=c+dr[1];if(nr>=0&&nr<n&&nc>=0&&nc<n&&!vis[nr][nc])pq.offer(new int[]{Math.max(t,g[nr][nc]),nr,nc});}}
    return -1;
}

C++

#include <queue>
#include <vector>
using namespace std;
int swimInWater(vector<vector<int>>&g){
    int n=g.size(); vector<vector<bool>>vis(n,vector<bool>(n,false));
    priority_queue<tuple<int,int,int>,vector<tuple<int,int,int>>,greater<>>pq; pq.push({g[0][0],0,0});
    int d[]={-1,0,1,0,-1};
    while(!pq.empty()){auto[t,r,c]=pq.top();pq.pop();if(vis[r][c])continue;vis[r][c]=true;if(r==n-1&&c==n-1)return t;for(int i=0;i<4;i++){int nr=r+d[i],nc=c+d[i+1];if(nr>=0&&nr<n&&nc>=0&&nc<n&&!vis[nr][nc])pq.push({max(t,g[nr][nc]),nr,nc});}}
    return -1;
}

C

/* C: min-heap struct with max(t, grid[nr][nc]) priority */