幅優先探索 (BFS) で東と西の両方の海へ流れる場所を探す

[[0, 2], [1, 0], [1, 1],
 [1, 2], [2, 0], [2, 1],
 [2, 2]]

[[0, 0], [0, 1], [0, 2],
 [1, 0], [1, 2],
 [2, 0], [2, 1], [2, 2]]

from collections import deque
STEPS = [
    (1, 0), (-1, 0),
    (0, 1), (0, -1),
]


def reach(h, starts):
    m, n = len(h), len(h[0])
    seen = set(starts)
    queue = deque(starts)
    while queue:
        r, c = queue.popleft()
        here = h[r][c]
        for dr, dc in STEPS:
            a = r + dr
            b = c + dc
            if not 0 <= a < m:
                continue
            if not 0 <= b < n:
                continue
            if (a, b) in seen:
                continue
            if h[a][b] < here:
                continue
            seen.add((a, b))
            queue.append((a, b))
    return seen


def both_seas(heights):
    m = len(heights)
    n = len(heights[0])
    west = []
    east = []
    for r in range(m):
        west.append((r, 0))
        east.append((r, n - 1))
    for c in range(n):
        west.append((0, c))
        east.append((m - 1, c))
    a = reach(heights, west)
    b = reach(heights, east)
    both = a & b
    out = []
    for r in range(m):
        for c in range(n):
            if (r, c) in both:
                out += [[r, c]]
    return out

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

function reach(h, starts) {
  const n = h[0].length;
  const seen = new Set();
  for (const [r, c] of starts) {
    seen.add(r * n + c);
  }
  const queue = [...starts];
  let head = 0;
  while (head < queue.length) {
    const [r, c] = queue[head];
    head++;
    const here = h[r][c];
    for (const s of STEPS) {
      const a = r + s[0];
      const b = c + s[1];
      const v = h[a]?.[b] ?? -1;
      if (v < here) continue;
      const k = a * n + b;
      if (seen.has(k)) continue;
      seen.add(k);
      queue.push([a, b]);
    }
  }
  return seen;
}

function bothSeas(heights) {
  const h = heights;
  const m = h.length;
  const n = h[0].length;
  const west = [];
  const east = [];
  for (let r = 0; r < m; r++) {
    west.push([r, 0]);
    east.push([r, n - 1]);
  }
  for (let c = 0; c < n; c++) {
    west.push([0, c]);
    east.push([m - 1, c]);
  }
  const a = reach(h, west);
  const b = reach(h, east);
  const out = [];
  h.forEach((row, r) => {
    row.forEach((_, c) => {
      const k = r * n + c;
      if (!a.has(k)) return;
      if (!b.has(k)) return;
      out.push([r, c]);
    });
  });
  return out;
}

type cell = [2]int

var dirs = [4]cell{
	{1, 0}, {-1, 0},
	{0, 1}, {0, -1},
}

func reach(
	h [][]int, starts []cell,
) [][]bool {
	m, n := len(h), len(h[0])
	seen := make([][]bool, m)
	for r := range seen {
		seen[r] = make([]bool, n)
	}
	for _, p := range starts {
		seen[p[0]][p[1]] = true
	}
	queue := starts
	head := 0
	for head < len(queue) {
		p := queue[head]
		head++
		r, c := p[0], p[1]
		here := h[r][c]
		for _, d := range dirs {
			a, b := r+d[0], c+d[1]
			if a < 0 || a >= m {
				continue
			}
			if b < 0 || b >= n {
				continue
			}
			if seen[a][b] {
				continue
			}
			if h[a][b] < here {
				continue
			}
			seen[a][b] = true
			nx := cell{a, b}
			queue = append(queue, nx)
		}
	}
	return seen
}

func bothSeas(
	heights [][]int,
) [][]int {
	m := len(heights)
	n := len(heights[0])
	west := []cell{}
	east := []cell{}
	for r := 0; r < m; r++ {
		w := cell{r, 0}
		e := cell{r, n - 1}
		west = append(west, w)
		east = append(east, e)
	}
	for c := 0; c < n; c++ {
		w := cell{0, c}
		e := cell{m - 1, c}
		west = append(west, w)
		east = append(east, e)
	}
	a := reach(heights, west)
	b := reach(heights, east)
	out := [][]int{}
	for r := 0; r < m; r++ {
		for c := 0; c < n; c++ {
			if a[r][c] && b[r][c] {
				p := []int{r, c}
				out = append(out, p)
			}
		}
	}
	return out
}