ヒープで水位の上がる池を対角まで渡れるいちばん早い時刻を求める

from heapq import heappop
from heapq import heappush

STEPS = ((1, 0), (-1, 0),
         (0, 1), (0, -1))


def swim_time(grid):
    n = len(grid)
    seen = {(0, 0)}
    h = [(grid[0][0], 0, 0)]
    last = n - 1
    while True:
        t, r, c = heappop(h)
        if r == c == last:
            return t
        for dy, dx in STEPS:
            y = r + dy
            x = c + dx
            if y < 0 or y >= n:
                continue
            if x < 0 or x >= n:
                continue
            if (y, x) in seen:
                continue
            seen.add((y, x))
            v = grid[y][x]
            v = max(v, t)
            item = (v, y, x)
            heappush(h, item)

function swimTime(grid) {
  const n = grid.length;
  const seen = new Set([0]);
  const h = [
    [grid[0][0], 0, 0]];
  while (true) {
    const [t, r, c] = pop(h);
    if (r === n - 1 &&
      c === n - 1) {
      return t;
    }
    for (const [y, x] of [
      [r + 1, c], [r - 1, c],
      [r, c + 1], [r, c - 1],
    ]) {
      if (y < 0 || y >= n ||
        x < 0 || x >= n) {
        continue;
      }
      // マスの番号は y * n + x
      const id = y * n + x;
      if (seen.has(id)) {
        continue;
      }
      seen.add(id);
      const v = Math.max(
        t, grid[y][x]);
      push(h, [v, y, x]);
    }
  }
}

// [時刻, 行, 列] の小さい順のヒープ
function push(h, x) {
  h.push(x);
  let i = h.length - 1;
  while (i > 0) {
    const p = (i - 1) >> 1;
    if (h[p][0] <= h[i][0]) {
      return;
    }
    [h[p], h[i]] = [h[i], h[p]];
    i = p;
  }
}

function pop(h) {
  const top = h[0];
  const last = h.pop();
  if (h.length === 0) {
    return top;
  }
  h[0] = last;
  const n = h.length;
  let i = 0;
  while (true) {
    let s = i;
    const l = 2 * i + 1;
    const r = l + 1;
    if (l < n &&
      h[l][0] < h[s][0]) {
      s = l;
    }
    if (r < n &&
      h[r][0] < h[s][0]) {
      s = r;
    }
    if (s === i) {
      return top;
    }
    [h[s], h[i]] = [h[i], h[s]];
    i = s;
  }
}

import "container/heap"

// {時刻, 行, 列} の小さい順のヒープ
type pq [][3]int

func (h pq) Len() int {
	return len(h)
}

func (h pq) Less(
	i, j int,
) bool {
	return h[i][0] < h[j][0]
}

func (h pq) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *pq) Push(x any) {
	*h = append(*h, x.([3]int))
}

func (h *pq) Pop() any {
	old := *h
	x := old[len(old)-1]
	*h = old[:len(old)-1]
	return x
}

var steps = [][2]int{
	{1, 0}, {-1, 0},
	{0, 1}, {0, -1},
}

func swimTime(
	grid [][]int,
) int {
	n := len(grid)
	seen := make([][]bool, n)
	for i := range seen {
		seen[i] = make([]bool, n)
	}
	seen[0][0] = true
	h := &pq{{grid[0][0], 0, 0}}
	for {
		top := heap.Pop(h).([3]int)
		t := top[0]
		r, c := top[1], top[2]
		if r == n-1 && c == n-1 {
			return t
		}
		for _, d := range steps {
			y, x := r+d[0], c+d[1]
			if y < 0 || y >= n ||
				x < 0 || x >= n ||
				seen[y][x] {
				continue
			}
			seen[y][x] = true
			v := max(t, grid[y][x])
			heap.Push(h,
				[3]int{v, y, x})
		}
	}
}