Swim in Rising Water
Problem
Given an n x n grid of elevations, find the minimum time t such that we can travel from (0,0) to (n-1,n-1), only entering cells with elevation <= t.
grid=[[0,2],[1,3]]3import heapq
def swimInWater(grid):
n = len(grid)
seen = {(0,0)}
h = [(grid[0][0], 0, 0)]
while h:
t, r, c = heapq.heappop(h)
if r == 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 seen:
seen.add((nr,nc))
heapq.heappush(h, (max(t, grid[nr][nc]), nr, nc))function swimInWater(grid) {
const n = grid.length;
const seen = new Set(["0,0"]);
const h = [[grid[0][0], 0, 0]];
const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
while (h.length) {
h.sort((a,b) => a[0]-b[0]);
const [t, r, c] = h.shift();
if (r === n-1 && c === n-1) return t;
for (const [dr,dc] of dirs) {
const nr = r+dr, nc = c+dc, key = nr+","+nc;
if (nr>=0 && nr<n && nc>=0 && nc<n && !seen.has(key)) {
seen.add(key);
h.push([Math.max(t, grid[nr][nc]), nr, nc]);
}
}
}
}int swimInWater(int[][] grid) {
int n = grid.length;
boolean[][] seen = new boolean[n][n];
PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> a[0]-b[0]);
pq.offer(new int[]{grid[0][0], 0, 0}); seen[0][0] = true;
int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
while (!pq.isEmpty()) {
int[] cur = pq.poll();
int t = cur[0], r = cur[1], c = cur[2];
if (r == n-1 && c == n-1) return t;
for (int[] d : dirs) {
int nr = r+d[0], nc = c+d[1];
if (nr>=0 && nr<n && nc>=0 && nc<n && !seen[nr][nc]) {
seen[nr][nc] = true;
pq.offer(new int[]{Math.max(t, grid[nr][nc]), nr, nc});
}
}
}
return -1;
}int swimInWater(vector<vector<int>>& grid) {
int n = grid.size();
vector<vector<bool>> seen(n, vector<bool>(n, false));
priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, greater<>> pq;
pq.push({grid[0][0], 0, 0}); seen[0][0] = true;
int dr[] = {1,-1,0,0}, dc[] = {0,0,1,-1};
while (!pq.empty()) {
auto [t, r, c] = pq.top(); pq.pop();
if (r == n-1 && c == n-1) return t;
for (int k = 0; k < 4; k++) {
int nr = r+dr[k], nc = c+dc[k];
if (nr>=0 && nr<n && nc>=0 && nc<n && !seen[nr][nc]) {
seen[nr][nc] = true;
pq.push({max(t, grid[nr][nc]), nr, nc});
}
}
}
return -1;
}Explanation
The water rises over time, and at time t you can stand on any cell whose elevation is <= t. We want the smallest time that still lets us reach the far corner. The trick is to think about the highest cell you are forced to cross on a path: the answer is the path whose worst (highest) cell is as low as possible.
This is a Dijkstra-style search with a min-heap. Each heap entry is (t, r, c) where t is the largest elevation seen so far on the best route to that cell. We always expand the cell with the smallest such t first.
When we step to a neighbor, the cost of that route becomes max(t, grid[nr][nc]) — either the bottleneck we already had, or this new cell if it is higher. We mark cells as seen so we never process one twice.
The moment we pop the target cell (n-1, n-1) from the heap, its t is the answer, because the heap always hands back the lowest possible bottleneck first.
Example: grid = [[0,2],[1,3]]. Starting at 0, both ways into the bottom-right corner must pass through a 3, so the minimum time is 3.