778. Swim rising water

778_solution1_dijkstra.c

#include <stdbool.h>
#include <stdlib.h>

typedef struct {
  int elev, r, c;
} Entry;

static void push(Entry *heap, int *len, Entry e) {
  int i = (*len)++;
  while (i > 0 && e.elev < heap[(i - 1) / 2].elev) {
    heap[i] = heap[(i - 1) / 2];
    i = (i - 1) / 2;
  }
  heap[i] = e;
}

static Entry pop(Entry *heap, int *len) {
  Entry top = heap[0], last = heap[--(*len)];
  int i = 0;
  for (;;) {
    int child = 2 * i + 1;
    if (child >= *len)
      break;
    if (child + 1 < *len && heap[child + 1].elev < heap[child].elev)
      child++;
    if (heap[child].elev >= last.elev)
      break;
    heap[i] = heap[child];
    i = child;
  }
  heap[i] = last;
  return top;
}

int swimInWater(int **grid, int gridSize, int *gridColSize) {
  (void)gridColSize; // square grid
  int n = gridSize;
  bool *visited = calloc(n * n, sizeof(bool));
  Entry *heap = malloc(n * n * sizeof(Entry)); // each cell is pushed once
  int len = 0;
  int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

  push(heap, &len, (Entry){grid[0][0], 0, 0});
  visited[0] = true;
  int t = 0, ans = -1;

  while (len > 0) {
    Entry e = pop(heap, &len);
    if (e.elev > t)
      t = e.elev;
    if (e.r == n - 1 && e.c == n - 1) {
      ans = t;
      break;
    }

    for (int d = 0; d < 4; d++) {
      int nr = e.r + dirs[d][0], nc = e.c + dirs[d][1];
      if (nr < 0 || nc < 0 || nr >= n || nc >= n || visited[nr * n + nc])
        continue;
      visited[nr * n + nc] = true;
      push(heap, &len, (Entry){grid[nr][nc], nr, nc});
    }
  }

  free(visited);
  free(heap);
  return ans;
}

778_solution2_binary_search.c

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

static int n;
static int **g;
static bool *visited;
static int *queue; // cell indices r * n + c

static bool canReach(int t) {
  if (g[0][0] > t)
    return false;
  memset(visited, 0, n * n * sizeof(bool));
  int head = 0, tail = 0;
  queue[tail++] = 0;
  visited[0] = true;
  int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

  while (head < tail) {
    int r = queue[head] / n, c = queue[head] % n;
    head++;
    if (r == n - 1 && c == n - 1)
      return true;
    for (int d = 0; d < 4; d++) {
      int nr = r + dirs[d][0], nc = c + dirs[d][1];
      if (nr < 0 || nc < 0 || nr >= n || nc >= n)
        continue;
      if (visited[nr * n + nc] || g[nr][nc] > t)
        continue;
      visited[nr * n + nc] = true;
      queue[tail++] = nr * n + nc;
    }
  }
  return false;
}

int swimInWater(int **grid, int gridSize, int *gridColSize) {
  (void)gridColSize; // square grid
  n = gridSize;
  g = grid;
  visited = malloc(n * n * sizeof(bool));
  queue = malloc(n * n * sizeof(int));

  int lo = 0, hi = n * n - 1;
  while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    if (canReach(mid))
      hi = mid; // works: try lower
    else
      lo = mid + 1; // fails: need more water
  }

  free(visited);
  free(queue);
  return lo;
}

778_solution3_union_find.c

#include <stdlib.h>

static int *parent, *rnk;

static int find(int x) {
  while (parent[x] != x) {
    parent[x] = parent[parent[x]]; // path halving
    x = parent[x];
  }
  return x;
}

static void unite(int a, int b) {
  a = find(a);
  b = find(b);
  if (a == b)
    return;
  if (rnk[a] < rnk[b]) {
    int t = a;
    a = b;
    b = t;
  }
  parent[b] = a;
  if (rnk[a] == rnk[b])
    rnk[a]++;
}

int swimInWater(int **grid, int gridSize, int *gridColSize) {
  (void)gridColSize; // square grid
  int n = gridSize;
  parent = malloc(n * n * sizeof(int));
  rnk = calloc(n * n, sizeof(int));
  for (int i = 0; i < n * n; i++)
    parent[i] = i;

  // pos[v] = cell index holding elevation v
  int *pos = malloc(n * n * sizeof(int));
  for (int r = 0; r < n; r++)
    for (int c = 0; c < n; c++)
      pos[grid[r][c]] = r * n + c;

  int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
  int ans = -1;

  for (int t = 0; t < n * n && ans == -1; t++) {
    int r = pos[t] / n, c = pos[t] % n; // this cell becomes submerged
    for (int d = 0; d < 4; d++) {
      int nr = r + dirs[d][0], nc = c + dirs[d][1];
      if (nr < 0 || nc < 0 || nr >= n || nc >= n)
        continue;
      if (grid[nr][nc] <= t) // neighbor already submerged
        unite(r * n + c, nr * n + nc);
    }
    if (find(0) == find(n * n - 1))
      ans = t;
  }

  free(parent);
  free(rnk);
  free(pos);
  return ans;
}

778_solution1_dijkstra.cpp

#include <algorithm>
#include <array>
#include <functional>
#include <queue>
#include <vector>

using namespace std;

class Solution {
public:
  int swimInWater(vector<vector<int>> &grid) {
    int n = grid.size();
    vector<vector<bool>> visited(n, vector<bool>(n, false));
    priority_queue<array<int, 3>, vector<array<int, 3>>, greater<>>
        pq; // {elev, r, c}
    int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    pq.push({grid[0][0], 0, 0});
    visited[0][0] = true;
    int t = 0;

    while (!pq.empty()) {
      auto [elev, r, c] = pq.top();
      pq.pop();
      t = max(t, elev);
      if (r == n - 1 && c == n - 1)
        return t;

      for (auto &d : dirs) {
        int nr = r + d[0], nc = c + d[1];
        if (nr < 0 || nc < 0 || nr >= n || nc >= n || visited[nr][nc])
          continue;
        visited[nr][nc] = true;
        pq.push({grid[nr][nc], nr, nc});
      }
    }
    return -1;
  }
};

778_solution2_binary_search.cpp

#include <queue>
#include <utility>
#include <vector>

using namespace std;

class Solution {
  int n;
  vector<vector<int>> *g;

  bool canReach(int t) {
    auto &grid = *g;
    if (grid[0][0] > t)
      return false;
    vector<vector<bool>> visited(n, vector<bool>(n, false));
    queue<pair<int, int>> q;
    q.push({0, 0});
    visited[0][0] = true;
    int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    while (!q.empty()) {
      auto [r, c] = q.front();
      q.pop();
      if (r == n - 1 && c == n - 1)
        return true;
      for (auto &d : dirs) {
        int nr = r + d[0], nc = c + d[1];
        if (nr < 0 || nc < 0 || nr >= n || nc >= n)
          continue;
        if (visited[nr][nc] || grid[nr][nc] > t)
          continue;
        visited[nr][nc] = true;
        q.push({nr, nc});
      }
    }
    return false;
  }

public:
  int swimInWater(vector<vector<int>> &grid) {
    n = grid.size();
    g = &grid;
    int lo = 0, hi = n * n - 1;
    while (lo < hi) {
      int mid = lo + (hi - lo) / 2;
      if (canReach(mid))
        hi = mid; // works: try lower
      else
        lo = mid + 1; // fails: need more water
    }
    return lo;
  }
};

778_solution3_union_find.cpp

#include <numeric>
#include <utility>
#include <vector>

using namespace std;

class Solution {
  vector<int> parent, rnk;

  int find(int x) {
    while (parent[x] != x) {
      parent[x] = parent[parent[x]]; // path halving
      x = parent[x];
    }
    return x;
  }

  void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b)
      return;
    if (rnk[a] < rnk[b])
      swap(a, b);
    parent[b] = a;
    if (rnk[a] == rnk[b])
      rnk[a]++;
  }

public:
  int swimInWater(vector<vector<int>> &grid) {
    int n = grid.size();
    parent.resize(n * n);
    rnk.assign(n * n, 0);
    iota(parent.begin(), parent.end(), 0);

    // pos[v] = cell index holding elevation v
    vector<int> pos(n * n);
    for (int r = 0; r < n; r++)
      for (int c = 0; c < n; c++)
        pos[grid[r][c]] = r * n + c;

    int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    for (int t = 0; t < n * n; t++) {
      int r = pos[t] / n, c = pos[t] % n; // this cell becomes submerged
      for (auto &d : dirs) {
        int nr = r + d[0], nc = c + d[1];
        if (nr < 0 || nc < 0 || nr >= n || nc >= n)
          continue;
        if (grid[nr][nc] <= t) // neighbor already submerged
          unite(r * n + c, nr * n + nc);
      }
      if (find(0) == find(n * n - 1))
        return t;
    }
    return -1;
  }
};

778_solution1_dijkstra.go

package graphs

import "container/heap"

type cell struct{ elev, r, c int }

type cellHeap []cell

func (h cellHeap) Len() int           { return len(h) }
func (h cellHeap) Less(i, j int) bool { return h[i].elev < h[j].elev }
func (h cellHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *cellHeap) Push(x any)        { *h = append(*h, x.(cell)) }
func (h *cellHeap) Pop() any {
    old := *h
    x := old[len(old)-1]
    *h = old[:len(old)-1]
    return x
}

func swimInWater(grid [][]int) int {
    n := len(grid)
    visited := make([][]bool, n)
    for i := range visited {
        visited[i] = make([]bool, n)
    }
    pq := &cellHeap{}
    dirs := [4][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}

    heap.Push(pq, cell{grid[0][0], 0, 0})
    visited[0][0] = true
    t := 0

    for pq.Len() > 0 {
        e := heap.Pop(pq).(cell)
        t = max(t, e.elev)
        if e.r == n-1 && e.c == n-1 {
            return t
        }

        for _, d := range dirs {
            nr, nc := e.r+d[0], e.c+d[1]
            if nr < 0 || nc < 0 || nr >= n || nc >= n || visited[nr][nc] {
                continue
            }
            visited[nr][nc] = true
            heap.Push(pq, cell{grid[nr][nc], nr, nc})
        }
    }
    return -1
}

778_solution2_binary_search.go

package graphs

func swimInWater(grid [][]int) int {
    n := len(grid)
    dirs := [4][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}

    canReach := func(t int) bool {
        if grid[0][0] > t {
            return false
        }
        visited := make([][]bool, n)
        for i := range visited {
            visited[i] = make([]bool, n)
        }
        q := [][2]int{{0, 0}}
        visited[0][0] = true

        for len(q) > 0 {
            r, c := q[0][0], q[0][1]
            q = q[1:]
            if r == n-1 && c == n-1 {
                return true
            }
            for _, d := range dirs {
                nr, nc := r+d[0], c+d[1]
                if nr < 0 || nc < 0 || nr >= n || nc >= n {
                    continue
                }
                if visited[nr][nc] || grid[nr][nc] > t {
                    continue
                }
                visited[nr][nc] = true
                q = append(q, [2]int{nr, nc})
            }
        }
        return false
    }

    lo, hi := 0, n*n-1
    for lo < hi {
        mid := lo + (hi-lo)/2
        if canReach(mid) {
            hi = mid // works: try lower
        } else {
            lo = mid + 1 // fails: need more water
        }
    }
    return lo
}

778_solution3_union_find.go

package graphs

func swimInWater(grid [][]int) int {
    n := len(grid)
    parent := make([]int, n*n)
    rnk := make([]int, n*n)
    for i := range parent {
        parent[i] = i
    }

    find := func(x int) int {
        for parent[x] != x {
            parent[x] = parent[parent[x]] // path halving
            x = parent[x]
        }
        return x
    }

    unite := func(a, b int) {
        a, b = find(a), find(b)
        if a == b {
            return
        }
        if rnk[a] < rnk[b] {
            a, b = b, a
        }
        parent[b] = a
        if rnk[a] == rnk[b] {
            rnk[a]++
        }
    }

    // pos[v] = cell index holding elevation v
    pos := make([]int, n*n)
    for r := 0; r < n; r++ {
        for c := 0; c < n; c++ {
            pos[grid[r][c]] = r*n + c
        }
    }

    dirs := [4][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}

    for t := 0; t < n*n; t++ {
        r, c := pos[t]/n, pos[t]%n // this cell becomes submerged
        for _, d := range dirs {
            nr, nc := r+d[0], c+d[1]
            if nr < 0 || nc < 0 || nr >= n || nc >= n {
                continue
            }
            if grid[nr][nc] <= t { // neighbor already submerged
                unite(r*n+c, nr*n+nc)
            }
        }
        if find(0) == find(n*n-1) {
            return t
        }
    }
    return -1
}

778_solution1_dijkstra.java

import java.util.PriorityQueue;

class Solution {
    public int swimInWater(int[][] grid) {
        int n = grid.length;
        boolean[][] visited = new boolean[n][n];
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0])); // {elev, r, c}
        int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

        pq.add(new int[] { grid[0][0], 0, 0 });
        visited[0][0] = true;
        int t = 0;

        while (!pq.isEmpty()) {
            int[] e = pq.poll();
            int elev = e[0], r = e[1], c = e[2];
            t = Math.max(t, elev);
            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 || nc < 0 || nr >= n || nc >= n || visited[nr][nc])
                    continue;
                visited[nr][nc] = true;
                pq.add(new int[] { grid[nr][nc], nr, nc });
            }
        }
        return -1;
    }
}

778_solution2_binary_search.java

import java.util.ArrayDeque;
import java.util.Queue;

class Solution {
    private int n;
    private int[][] grid;

    private boolean canReach(int t) {
        if (grid[0][0] > t)
            return false;
        boolean[][] visited = new boolean[n][n];
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[] { 0, 0 });
        visited[0][0] = true;
        int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int r = cur[0], c = cur[1];
            if (r == n - 1 && c == n - 1)
                return true;
            for (int[] d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr < 0 || nc < 0 || nr >= n || nc >= n)
                    continue;
                if (visited[nr][nc] || grid[nr][nc] > t)
                    continue;
                visited[nr][nc] = true;
                q.add(new int[] { nr, nc });
            }
        }
        return false;
    }

    public int swimInWater(int[][] grid) {
        this.n = grid.length;
        this.grid = grid;
        int lo = 0, hi = n * n - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (canReach(mid))
                hi = mid; // works: try lower
            else
                lo = mid + 1; // fails: need more water
        }
        return lo;
    }
}

778_solution3_union_find.java

class Solution {
    private int[] parent, rnk;

    private int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]]; // path halving
            x = parent[x];
        }
        return x;
    }

    private void unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b)
            return;
        if (rnk[a] < rnk[b]) {
            int t = a;
            a = b;
            b = t;
        }
        parent[b] = a;
        if (rnk[a] == rnk[b])
            rnk[a]++;
    }

    public int swimInWater(int[][] grid) {
        int n = grid.length;
        parent = new int[n * n];
        rnk = new int[n * n];
        for (int i = 0; i < n * n; i++)
            parent[i] = i;

        // pos[v] = cell index holding elevation v
        int[] pos = new int[n * n];
        for (int r = 0; r < n; r++)
            for (int c = 0; c < n; c++)
                pos[grid[r][c]] = r * n + c;

        int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

        for (int t = 0; t < n * n; t++) {
            int r = pos[t] / n, c = pos[t] % n; // this cell becomes submerged
            for (int[] d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr < 0 || nc < 0 || nr >= n || nc >= n)
                    continue;
                if (grid[nr][nc] <= t) // neighbor already submerged
                    unite(r * n + c, nr * n + nc);
            }
            if (find(0) == find(n * n - 1))
                return t;
        }
        return -1;
    }
}

778_solution1_dijkstra.js

/**
 * @param {number[][]} grid
 * @return {number}
 */
var swimInWater = function (grid) {
  const n = grid.length;
  const visited = Array.from({ length: n }, () => new Array(n).fill(false));
  const pq = new MinHeap((a, b) => a[0] - b[0]); // [elev, r, c]
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];

  pq.push([grid[0][0], 0, 0]);
  visited[0][0] = true;
  let t = 0;

  while (pq.size()) {
    const [elev, r, c] = pq.pop();
    t = Math.max(t, elev);
    if (r === n - 1 && c === n - 1) return t;

    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nc < 0 || nr >= n || nc >= n || visited[nr][nc]) continue;
      visited[nr][nc] = true;
      pq.push([grid[nr][nc], nr, nc]);
    }
  }
  return -1;
};

// JS has no built-in heap
class MinHeap {
  constructor(cmp) {
    this.a = [];
    this.cmp = cmp;
  }
  size() {
    return this.a.length;
  }
  push(x) {
    const a = this.a;
    a.push(x);
    for (let i = a.length - 1; i > 0; ) {
      const p = (i - 1) >> 1;
      if (this.cmp(a[i], a[p]) >= 0) break;
      [a[i], a[p]] = [a[p], a[i]];
      i = p;
    }
  }
  pop() {
    const a = this.a;
    const top = a[0];
    const last = a.pop();
    if (a.length) {
      a[0] = last;
      for (let i = 0; ; ) {
        let c = 2 * i + 1;
        if (c >= a.length) break;
        if (c + 1 < a.length && this.cmp(a[c + 1], a[c]) < 0) c++;
        if (this.cmp(a[c], a[i]) >= 0) break;
        [a[i], a[c]] = [a[c], a[i]];
        i = c;
      }
    }
    return top;
  }
}

778_solution2_binary_search.js

/**
 * @param {number[][]} grid
 * @return {number}
 */
var swimInWater = function (grid) {
  const n = grid.length;
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];

  const canReach = (t) => {
    if (grid[0][0] > t) return false;
    const visited = Array.from({ length: n }, () => new Array(n).fill(false));
    const q = [[0, 0]];
    visited[0][0] = true;

    for (let head = 0; head < q.length; head++) {
      const [r, c] = q[head];
      if (r === n - 1 && c === n - 1) return true;
      for (const [dr, dc] of dirs) {
        const nr = r + dr, nc = c + dc;
        if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue;
        if (visited[nr][nc] || grid[nr][nc] > t) continue;
        visited[nr][nc] = true;
        q.push([nr, nc]);
      }
    }
    return false;
  };

  let lo = 0, hi = n * n - 1;
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (canReach(mid)) hi = mid; // works: try lower
    else lo = mid + 1; // fails: need more water
  }
  return lo;
};

778_solution3_union_find.js

/**
 * @param {number[][]} grid
 * @return {number}
 */
var swimInWater = function (grid) {
  const n = grid.length;
  const parent = Array.from({ length: n * n }, (_, i) => i);
  const rnk = new Array(n * n).fill(0);

  const find = (x) => {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]]; // path halving
      x = parent[x];
    }
    return x;
  };

  const unite = (a, b) => {
    a = find(a);
    b = find(b);
    if (a === b) return;
    if (rnk[a] < rnk[b]) [a, b] = [b, a];
    parent[b] = a;
    if (rnk[a] === rnk[b]) rnk[a]++;
  };

  // pos[v] = cell index holding elevation v
  const pos = new Array(n * n);
  for (let r = 0; r < n; r++) for (let c = 0; c < n; c++) pos[grid[r][c]] = r * n + c;

  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];

  for (let t = 0; t < n * n; t++) {
    const r = Math.floor(pos[t] / n), c = pos[t] % n; // this cell becomes submerged
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue;
      if (grid[nr][nc] <= t) unite(r * n + c, nr * n + nc); // neighbor already submerged
    }
    if (find(0) === find(n * n - 1)) return t;
  }
  return -1;
};

778_solution1_dijkstra.py

import heapq
from typing import List


class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        n = len(grid)
        visited = [[False] * n for _ in range(n)]
        pq = [(grid[0][0], 0, 0)]  # (elev, r, c)
        visited[0][0] = True
        t = 0

        while pq:
            elev, r, c = heapq.heappop(pq)
            t = max(t, elev)
            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 nr < 0 or nc < 0 or nr >= n or nc >= n or visited[nr][nc]:
                    continue
                visited[nr][nc] = True
                heapq.heappush(pq, (grid[nr][nc], nr, nc))
        return -1

778_solution2_binary_search.py

from collections import deque
from typing import List


class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        n = len(grid)

        def can_reach(t: int) -> bool:
            if grid[0][0] > t:
                return False
            visited = [[False] * n for _ in range(n)]
            q = deque([(0, 0)])
            visited[0][0] = True

            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 nr < 0 or nc < 0 or nr >= n or nc >= n:
                        continue
                    if visited[nr][nc] or grid[nr][nc] > t:
                        continue
                    visited[nr][nc] = True
                    q.append((nr, nc))
            return False

        lo, hi = 0, n * n - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if can_reach(mid):
                hi = mid  # works: try lower
            else:
                lo = mid + 1  # fails: need more water
        return lo

778_solution3_union_find.py

from typing import List


class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        n = len(grid)
        parent = list(range(n * n))
        rnk = [0] * (n * n)

        def find(x: int) -> int:
            while parent[x] != x:
                parent[x] = parent[parent[x]]  # path halving
                x = parent[x]
            return x

        def unite(a: int, b: int) -> None:
            a, b = find(a), find(b)
            if a == b:
                return
            if rnk[a] < rnk[b]:
                a, b = b, a
            parent[b] = a
            if rnk[a] == rnk[b]:
                rnk[a] += 1

        # pos[v] = cell index holding elevation v
        pos = [0] * (n * n)
        for r in range(n):
            for c in range(n):
                pos[grid[r][c]] = r * n + c

        for t in range(n * n):
            r, c = divmod(pos[t], n)  # this cell becomes submerged
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = r + dr, c + dc
                if nr < 0 or nc < 0 or nr >= n or nc >= n:
                    continue
                if grid[nr][nc] <= t:  # neighbor already submerged
                    unite(r * n + c, nr * n + nc)
            if find(0) == find(n * n - 1):
                return t
        return -1

778_solution1_dijkstra.rs

use std::cmp::Reverse;
use std::collections::BinaryHeap;

impl Solution {
    pub fn swim_in_water(grid: Vec<Vec<i32>>) -> i32 {
        let n = grid.len();
        let mut visited = vec![vec![false; n]; n];
        let mut pq = BinaryHeap::new(); // Reverse((elev, r, c))
        let dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)];

        pq.push(Reverse((grid[0][0], 0usize, 0usize)));
        visited[0][0] = true;
        let mut t = 0;

        while let Some(Reverse((elev, r, c))) = pq.pop() {
            t = t.max(elev);
            if r == n - 1 && c == n - 1 {
                return t;
            }

            for (dr, dc) in dirs {
                let (nr, nc) = (r as i32 + dr, c as i32 + dc);
                if nr < 0 || nc < 0 || nr >= n as i32 || nc >= n as i32 {
                    continue;
                }
                let (nr, nc) = (nr as usize, nc as usize);
                if visited[nr][nc] {
                    continue;
                }
                visited[nr][nc] = true;
                pq.push(Reverse((grid[nr][nc], nr, nc)));
            }
        }
        -1
    }
}

778_solution2_binary_search.rs

use std::collections::VecDeque;

impl Solution {
    pub fn swim_in_water(grid: Vec<Vec<i32>>) -> i32 {
        let n = grid.len() as i32;
        let (mut lo, mut hi) = (0, n * n - 1);
        while lo < hi {
            let mid = lo + (hi - lo) / 2;
            if Self::can_reach(&grid, mid) {
                hi = mid; // works: try lower
            } else {
                lo = mid + 1; // fails: need more water
            }
        }
        lo
    }

    fn can_reach(grid: &[Vec<i32>], t: i32) -> bool {
        let n = grid.len();
        if grid[0][0] > t {
            return false;
        }
        let mut visited = vec![vec![false; n]; n];
        let mut q = VecDeque::from([(0usize, 0usize)]);
        visited[0][0] = true;
        let dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)];

        while let Some((r, c)) = q.pop_front() {
            if r == n - 1 && c == n - 1 {
                return true;
            }
            for (dr, dc) in dirs {
                let (nr, nc) = (r as i32 + dr, c as i32 + dc);
                if nr < 0 || nc < 0 || nr >= n as i32 || nc >= n as i32 {
                    continue;
                }
                let (nr, nc) = (nr as usize, nc as usize);
                if visited[nr][nc] || grid[nr][nc] > t {
                    continue;
                }
                visited[nr][nc] = true;
                q.push_back((nr, nc));
            }
        }
        false
    }
}

778_solution3_union_find.rs

impl Solution {
    pub fn swim_in_water(grid: Vec<Vec<i32>>) -> i32 {
        let n = grid.len();
        let mut parent: Vec<usize> = (0..n * n).collect();
        let mut rnk = vec![0u32; n * n];

        // pos[v] = cell index holding elevation v
        let mut pos = vec![0; n * n];
        for r in 0..n {
            for c in 0..n {
                pos[grid[r][c] as usize] = r * n + c;
            }
        }

        let dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)];

        for t in 0..n * n {
            let (r, c) = (pos[t] / n, pos[t] % n); // this cell becomes submerged
            for (dr, dc) in dirs {
                let (nr, nc) = (r as i32 + dr, c as i32 + dc);
                if nr < 0 || nc < 0 || nr >= n as i32 || nc >= n as i32 {
                    continue;
                }
                let (nr, nc) = (nr as usize, nc as usize);
                if grid[nr][nc] as usize <= t {
                    // neighbor already submerged
                    Self::unite(&mut parent, &mut rnk, r * n + c, nr * n + nc);
                }
            }
            if Self::find(&mut parent, 0) == Self::find(&mut parent, n * n - 1) {
                return t as i32;
            }
        }
        -1
    }

    fn find(parent: &mut [usize], mut x: usize) -> usize {
        while parent[x] != x {
            parent[x] = parent[parent[x]]; // path halving
            x = parent[x];
        }
        x
    }

    fn unite(parent: &mut [usize], rnk: &mut [u32], a: usize, b: usize) {
        let (mut a, mut b) = (Self::find(parent, a), Self::find(parent, b));
        if a == b {
            return;
        }
        if rnk[a] < rnk[b] {
            std::mem::swap(&mut a, &mut b);
        }
        parent[b] = a;
        if rnk[a] == rnk[b] {
            rnk[a] += 1;
        }
    }
}