"""
LC 417 — Pacific Atlantic Water Flow.

Multi-source BFS with edge-direction inversion.

Implementations:
    1. pacific_atlantic_bfs   — multi-source BFS from each ocean's border, walking UPHILL.
    2. pacific_atlantic_dfs   — same algorithm via recursion.
    3. pacific_atlantic_brute — O((MN)^2) per-cell forward BFS. Oracle.

INVARIANT (multi-source BFS): when reverse-walking from oceans, neighbor must be
                              heights[nr][nc] >= heights[r][c] (uphill traversal).
INVARIANT: visited marked at enqueue, never at dequeue.
"""

from __future__ import annotations

import random
import sys
from collections import deque

sys.setrecursionlimit(50_000)

DIRS: tuple[tuple[int, int], ...] = ((1, 0), (-1, 0), (0, 1), (0, -1))


# ----------------------------------------------------------------------
# Solution A — Multi-source BFS (canonical).
# ----------------------------------------------------------------------

def pacific_atlantic_bfs(heights: list[list[int]]) -> list[list[int]]:
    if not heights or not heights[0]:
        return []
    m, n = len(heights), len(heights[0])
    pac = [[False] * n for _ in range(m)]
    atl = [[False] * n for _ in range(m)]

    def bfs(starts: list[tuple[int, int]], reachable: list[list[bool]]) -> None:
        q: deque[tuple[int, int]] = deque()
        for r, c in starts:
            if not reachable[r][c]:
                reachable[r][c] = True
                q.append((r, c))
        while q:
            r, c = q.popleft()
            h = heights[r][c]
            for dr, dc in DIRS:
                nr, nc = r + dr, c + dc
                if (0 <= nr < m and 0 <= nc < n
                        and not reachable[nr][nc]
                        and heights[nr][nc] >= h):  # uphill (reversed flow)
                    reachable[nr][nc] = True
                    q.append((nr, nc))

    pac_starts = [(0, c) for c in range(n)] + [(r, 0) for r in range(m)]
    atl_starts = [(m - 1, c) for c in range(n)] + [(r, n - 1) for r in range(m)]
    bfs(pac_starts, pac)
    bfs(atl_starts, atl)

    return [[r, c] for r in range(m) for c in range(n) if pac[r][c] and atl[r][c]]


# ----------------------------------------------------------------------
# Solution B — Multi-source DFS.
# ----------------------------------------------------------------------

def pacific_atlantic_dfs(heights: list[list[int]]) -> list[list[int]]:
    if not heights or not heights[0]:
        return []
    m, n = len(heights), len(heights[0])
    pac = [[False] * n for _ in range(m)]
    atl = [[False] * n for _ in range(m)]

    def dfs(r: int, c: int, reachable: list[list[bool]]) -> None:
        reachable[r][c] = True
        h = heights[r][c]
        for dr, dc in DIRS:
            nr, nc = r + dr, c + dc
            if (0 <= nr < m and 0 <= nc < n
                    and not reachable[nr][nc]
                    and heights[nr][nc] >= h):
                dfs(nr, nc, reachable)

    for c in range(n):
        if not pac[0][c]:
            dfs(0, c, pac)
        if not atl[m - 1][c]:
            dfs(m - 1, c, atl)
    for r in range(m):
        if not pac[r][0]:
            dfs(r, 0, pac)
        if not atl[r][n - 1]:
            dfs(r, n - 1, atl)

    return [[r, c] for r in range(m) for c in range(n) if pac[r][c] and atl[r][c]]


# ----------------------------------------------------------------------
# Solution C — Brute oracle. O((MN)^2).
# ----------------------------------------------------------------------

def pacific_atlantic_brute(heights: list[list[int]]) -> list[list[int]]:
    if not heights or not heights[0]:
        return []
    m, n = len(heights), len(heights[0])

    def reaches_both(r0: int, c0: int) -> bool:
        # Forward BFS from (r0, c0): walk to neighbors with heights <=.
        visited = [[False] * n for _ in range(m)]
        visited[r0][c0] = True
        q: deque[tuple[int, int]] = deque([(r0, c0)])
        hit_pac = hit_atl = False
        while q and not (hit_pac and hit_atl):
            r, c = q.popleft()
            if r == 0 or c == 0:
                hit_pac = True
            if r == m - 1 or c == n - 1:
                hit_atl = True
            h = heights[r][c]
            for dr, dc in DIRS:
                nr, nc = r + dr, c + dc
                if (0 <= nr < m and 0 <= nc < n
                        and not visited[nr][nc]
                        and heights[nr][nc] <= h):  # forward flow: downhill (and equal)
                    visited[nr][nc] = True
                    q.append((nr, nc))
        return hit_pac and hit_atl

    return [[r, c] for r in range(m) for c in range(n) if reaches_both(r, c)]


# ----------------------------------------------------------------------
# Helpers.
# ----------------------------------------------------------------------

def random_heights(rng: random.Random, m: int, n: int, max_h: int = 10) -> list[list[int]]:
    return [[rng.randint(0, max_h) for _ in range(n)] for _ in range(m)]


def canon(result: list[list[int]]) -> list[tuple[int, int]]:
    return sorted((r, c) for r, c in result)


# ----------------------------------------------------------------------
# Stress test.
# ----------------------------------------------------------------------

def stress_test() -> None:
    rng = random.Random(42)
    n_iter = 100
    for _ in range(n_iter):
        m = rng.randint(1, 12)
        n = rng.randint(1, 12)
        heights = random_heights(rng, m, n, max_h=rng.randint(1, 8))
        a = canon(pacific_atlantic_bfs(heights))
        b = canon(pacific_atlantic_dfs(heights))
        c = canon(pacific_atlantic_brute(heights))
        assert a == b == c, (
            f"Disagreement:\nbfs={a}\ndfs={b}\nbrute={c}\nheights={heights}"
        )
    print(f"stress_test: {n_iter} random grids — multi-source BFS, multi-source DFS, "
          "and brute oracle all agree.")


# ----------------------------------------------------------------------
# Edge cases.
# ----------------------------------------------------------------------

def edge_cases() -> None:
    # Empty.
    for fn in (pacific_atlantic_bfs, pacific_atlantic_dfs, pacific_atlantic_brute):
        assert fn([]) == []
        assert fn([[]]) == []

    # 1x1: cell touches both oceans → answer is itself.
    g = [[5]]
    for fn in (pacific_atlantic_bfs, pacific_atlantic_dfs, pacific_atlantic_brute):
        assert canon(fn(g)) == [(0, 0)]

    # 1-row: every cell touches top (Pac) AND bottom (Atl), so all reach both? Yes — same row IS both edges.
    g = [[1, 2, 3, 4, 5]]
    for fn in (pacific_atlantic_bfs, pacific_atlantic_dfs, pacific_atlantic_brute):
        assert canon(fn(g)) == [(0, 0), (0, 1), (0, 2), (0, 3), (0, 4)]

    # 1-col: same logic.
    g = [[1], [2], [3]]
    for fn in (pacific_atlantic_bfs, pacific_atlantic_dfs, pacific_atlantic_brute):
        assert canon(fn(g)) == [(0, 0), (1, 0), (2, 0)]

    # All-equal: every cell drains both directions because equal-height flow is allowed.
    g = [[5] * 4 for _ in range(4)]
    expected = [(r, c) for r in range(4) for c in range(4)]
    for fn in (pacific_atlantic_bfs, pacific_atlantic_dfs, pacific_atlantic_brute):
        assert canon(fn(g)) == expected

    # LC canonical.
    g = [
        [1, 2, 2, 3, 5],
        [3, 2, 3, 4, 4],
        [2, 4, 5, 3, 1],
        [6, 7, 1, 4, 5],
        [5, 1, 1, 2, 4],
    ]
    expected_lc = [(0, 4), (1, 3), (1, 4), (2, 2), (3, 0), (3, 1), (4, 0)]
    for fn in (pacific_atlantic_bfs, pacific_atlantic_dfs, pacific_atlantic_brute):
        assert canon(fn(g)) == expected_lc

    # Monotone increasing along rows: only the top-right corner drains to Atlantic naturally,
    # but with reverse traversal we can verify.
    g = [[1, 2, 3], [2, 3, 4], [3, 4, 5]]
    a = canon(pacific_atlantic_bfs(g))
    b = canon(pacific_atlantic_brute(g))
    assert a == b

    print("edge_cases: PASS")


if __name__ == "__main__":
    edge_cases()
    stress_test()
    print("ALL TESTS PASSED")