Swim in Rising Water

// C++ — Dijkstra (minimize bottleneck)
int swimInWater(vector<vector<int>>& grid) {
    int n = grid.size();
    vector<vector<int>> dist(n, vector<int>(n, INT_MAX));
    priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, greater<>> minH;
    minH.push({grid[0][0], 0, 0});
    dist[0][0] = grid[0][0];
    int dx[]={0,0,1,-1}, dy[]={1,-1,0,0};
    while (!minH.empty()) {
        auto [d, r, c] = minH.top(); minH.pop();
        if (r==n-1&&c==n-1) return d;
        if (d > dist[r][c]) continue;
        for (int i=0;i<4;i++) {
            int nr=r+dx[i], nc=c+dy[i];
            if (nr<0||nr>=n||nc<0||nc>=n) continue;
            int nd = max(d, grid[nr][nc]);
            if (nd < dist[nr][nc]) { dist[nr][nc]=nd; minH.push({nd,nr,nc}); }
        }
    }
    return -1;
}

// Java
public int swimInWater(int[][] grid) {
    int n = grid.length;
    int[][] dist = new int[n][n];
    for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
    PriorityQueue<int[]> minH = new PriorityQueue<>(Comparator.comparingInt(a->a[0]));
    minH.offer(new int[]{grid[0][0], 0, 0});
    dist[0][0] = grid[0][0];
    int[]dx={0,0,1,-1},dy={1,-1,0,0};
    while (!minH.isEmpty()) {
        int[]p=minH.poll();
        if(p[1]==n-1&&p[2]==n-1)return p[0];
        if(p[0]>dist[p[1]][p[2]])continue;
        for(int d=0;d<4;d++){
            int nr=p[1]+dx[d],nc=p[2]+dy[d];
            if(nr<0||nr>=n||nc<0||nc>=n)continue;
            int nd=Math.max(p[0],grid[nr][nc]);
            if(nd<dist[nr][nc]){dist[nr][nc]=nd;minH.offer(new int[]{nd,nr,nc});}
        }
    }
    return -1;
}

# Python — Dijkstra
import heapq

def swimInWater(grid):
    n = len(grid)
    dist = [[float('inf')] * n for _ in range(n)]
    dist[0][0] = grid[0][0]
    heap = [(grid[0][0], 0, 0)]
    while heap:
        d, r, c = heapq.heappop(heap)
        if r == n-1 and c == n-1:
            return d
        if d > dist[r][c]:
            continue
        for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
            nr, nc = r+dr, c+dc
            if 0 <= nr < n and 0 <= nc < n:
                nd = max(d, grid[nr][nc])
                if nd < dist[nr][nc]:
                    dist[nr][nc] = nd
                    heapq.heappush(heap, (nd, nr, nc))
    return -1

// JavaScript — Binary search + BFS
function swimInWater(grid) {
    const n = grid.length;
    function canSwim(T) {
        if (grid[0][0] > T) return false;
        const vis = Array.from({length: n}, () => Array(n).fill(false));
        const q = [[0, 0]]; vis[0][0] = true;
        while (q.length) {
            const [r, c] = q.shift();
            if (r === n-1 && c === n-1) return true;
            for (const [dr, dc] of [[0,1],[0,-1],[1,0],[-1,0]]) {
                const nr = r+dr, nc = c+dc;
                if (nr>=0 && nr<n && nc>=0 && nc<n && !vis[nr][nc] && grid[nr][nc]<=T) {
                    vis[nr][nc] = true; q.push([nr, nc]);
                }
            }
        }
        return false;
    }
    let lo = 0, hi = n*n - 1;
    while (lo < hi) { const mid=(lo+hi)>>1; if(canSwim(mid))hi=mid;else lo=mid+1; }
    return lo;
}