"""
LC 200 — Number of Islands.

Four implementations:
    1. num_islands_dfs     — recursive DFS with visited matrix (canonical, small grids).
    2. num_islands_bfs     — iterative BFS with deque + mark-on-enqueue.
    3. num_islands_uf      — Union-Find with path compression + union by rank.
    4. num_islands_mutate  — DFS that mutates grid ('1' -> '0') as visited marker.

INVARIANT (all): each land cell is visited exactly once across the entire run.
INVARIANT (BFS): when a cell is appended to the queue, it is simultaneously marked visited.
                 This bounds the queue size by the frontier perimeter, not by O(MN).
"""

from __future__ import annotations

import random
import sys
from collections import deque

sys.setrecursionlimit(200_000)

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


# ----------------------------------------------------------------------
# Solution A — Recursive DFS with visited matrix.
# ----------------------------------------------------------------------

def num_islands_dfs(grid: list[list[str]]) -> int:
    if not grid or not grid[0]:
        return 0
    m, n = len(grid), len(grid[0])
    visited = [[False] * n for _ in range(m)]
    count = 0

    def dfs(r: int, c: int) -> None:
        # INVARIANT: caller has already marked (r, c) visited before calling.
        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 grid[nr][nc] == "1":
                visited[nr][nc] = True
                dfs(nr, nc)

    for r in range(m):
        for c in range(n):
            if grid[r][c] == "1" and not visited[r][c]:
                count += 1
                visited[r][c] = True
                dfs(r, c)
    return count


# ----------------------------------------------------------------------
# Solution B — Iterative BFS with mark-on-enqueue.
# ----------------------------------------------------------------------

def num_islands_bfs(grid: list[list[str]]) -> int:
    if not grid or not grid[0]:
        return 0
    m, n = len(grid), len(grid[0])
    visited = [[False] * n for _ in range(m)]
    count = 0

    for r0 in range(m):
        for c0 in range(n):
            if grid[r0][c0] != "1" or visited[r0][c0]:
                continue
            count += 1
            visited[r0][c0] = True
            q: deque[tuple[int, int]] = deque([(r0, c0)])
            while q:
                r, c = q.popleft()
                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 grid[nr][nc] == "1":
                        visited[nr][nc] = True  # mark on enqueue, not on dequeue
                        q.append((nr, nc))
    return count


# ----------------------------------------------------------------------
# Solution C — Union-Find (path compression + union by rank).
# ----------------------------------------------------------------------

class UnionFind:
    __slots__ = ("parent", "rank", "components")

    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.components = n

    def find(self, x: int) -> int:
        # iterative path compression
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != root:
            self.parent[x], x = root, self.parent[x]
        return root

    def union(self, a: int, b: int) -> bool:
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        self.components -= 1
        return True


def num_islands_uf(grid: list[list[str]]) -> int:
    if not grid or not grid[0]:
        return 0
    m, n = len(grid), len(grid[0])
    uf = UnionFind(m * n)
    # Start: treat every cell as its own component, then subtract water cells and merge land.
    water_count = 0
    for r in range(m):
        for c in range(n):
            if grid[r][c] == "0":
                water_count += 1
                continue
            idx = r * n + c
            # Look only up and left; symmetric edges covered.
            if r > 0 and grid[r - 1][c] == "1":
                uf.union(idx, (r - 1) * n + c)
            if c > 0 and grid[r][c - 1] == "1":
                uf.union(idx, r * n + (c - 1))
    return uf.components - water_count


# ----------------------------------------------------------------------
# Solution D — DFS that mutates the grid as visited marker.
# ----------------------------------------------------------------------

def num_islands_mutate(grid: list[list[str]]) -> int:
    if not grid or not grid[0]:
        return 0
    # Defensive: deep-copy so callers' tests don't see the mutation.
    grid = [row[:] for row in grid]
    m, n = len(grid), len(grid[0])
    count = 0

    def sink(r: int, c: int) -> None:
        # iterative DFS to avoid stack overflow on large grids
        stack = [(r, c)]
        grid[r][c] = "0"
        while stack:
            cr, cc = stack.pop()
            for dr, dc in DIRS:
                nr, nc = cr + dr, cc + dc
                if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == "1":
                    grid[nr][nc] = "0"
                    stack.append((nr, nc))

    for r in range(m):
        for c in range(n):
            if grid[r][c] == "1":
                count += 1
                sink(r, c)
    return count


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

def random_grid(rng: random.Random, m: int, n: int, land_prob: float) -> list[list[str]]:
    return [["1" if rng.random() < land_prob else "0" for _ in range(n)] for _ in range(m)]


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

def stress_test() -> None:
    rng = random.Random(42)
    n_iter = 1000
    for _ in range(n_iter):
        m = rng.randint(0, 12)
        n = rng.randint(0, 12)
        land_prob = rng.uniform(0.2, 0.8)
        grid = random_grid(rng, m, n, land_prob)
        # Make 4 independent copies because num_islands_mutate is destructive-internal but
        # we already deep-copy inside it; DFS/BFS/UF only read.
        a = num_islands_dfs(grid)
        b = num_islands_bfs(grid)
        c = num_islands_uf(grid)
        d = num_islands_mutate(grid)
        assert a == b == c == d, (
            f"Disagreement: dfs={a} bfs={b} uf={c} mutate={d}\ngrid={grid}"
        )
    print(f"stress_test: {n_iter} random grids — DFS / BFS / Union-Find / mutate all agree.")


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

def edge_cases() -> None:
    # Empty.
    for fn in (num_islands_dfs, num_islands_bfs, num_islands_uf, num_islands_mutate):
        assert fn([]) == 0
        assert fn([[]]) == 0

    # Single cells.
    for fn in (num_islands_dfs, num_islands_bfs, num_islands_uf, num_islands_mutate):
        assert fn([["1"]]) == 1
        assert fn([["0"]]) == 0

    # All water.
    g_water = [["0"] * 5 for _ in range(5)]
    for fn in (num_islands_dfs, num_islands_bfs, num_islands_uf, num_islands_mutate):
        assert fn(g_water) == 0

    # All land (one big island).
    g_land = [["1"] * 5 for _ in range(5)]
    for fn in (num_islands_dfs, num_islands_bfs, num_islands_uf, num_islands_mutate):
        assert fn(g_land) == 1

    # Canonical LC example 1.
    g1 = [
        ["1", "1", "1", "1", "0"],
        ["1", "1", "0", "1", "0"],
        ["1", "1", "0", "0", "0"],
        ["0", "0", "0", "0", "0"],
    ]
    for fn in (num_islands_dfs, num_islands_bfs, num_islands_uf, num_islands_mutate):
        assert fn(g1) == 1

    # Canonical LC example 2.
    g2 = [
        ["1", "1", "0", "0", "0"],
        ["1", "1", "0", "0", "0"],
        ["0", "0", "1", "0", "0"],
        ["0", "0", "0", "1", "1"],
    ]
    for fn in (num_islands_dfs, num_islands_bfs, num_islands_uf, num_islands_mutate):
        assert fn(g2) == 3

    # Diagonal-only "islands" (not connected under 4-conn).
    g3 = [
        ["1", "0", "1"],
        ["0", "1", "0"],
        ["1", "0", "1"],
    ]
    for fn in (num_islands_dfs, num_islands_bfs, num_islands_uf, num_islands_mutate):
        assert fn(g3) == 5

    # Path-shaped island that stresses recursion depth on the recursive variant.
    # Snake of length ~200; depth ≤ 200 << recursionlimit 200k.
    m, n = 10, 20
    snake = [["0"] * n for _ in range(m)]
    r, c, dr, dc = 0, 0, 0, 1
    for _ in range(m * n):
        snake[r][c] = "1"
        nr, nc = r + dr, c + dc
        if not (0 <= nr < m and 0 <= nc < n) or snake[nr][nc] == "1":
            # turn
            if dr == 0 and dc == 1:
                dr, dc = 1, 0
            elif dr == 1 and dc == 0:
                dr, dc = 0, -1
            elif dr == 0 and dc == -1:
                dr, dc = -1, 0
            else:
                dr, dc = 0, 1
            nr, nc = r + dr, c + dc
            if not (0 <= nr < m and 0 <= nc < n) or snake[nr][nc] == "1":
                break
        r, c = nr, nc
    for fn in (num_islands_dfs, num_islands_bfs, num_islands_uf, num_islands_mutate):
        assert fn(snake) == 1

    print("edge_cases: PASS")


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