"""
p76 — Dungeon Game (LeetCode 174, HARD).

Reverse DP. dp[i][j] = min health needed ENTERING (i,j) to survive to goal.
Recurrence:
    dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j])
with sentinel dp[m][n-1] = dp[m-1][n] = 1 (entering the princess cell already accounted).

Why max(1, ...): even if the cell gives a big bonus, knight must be alive (HP >= 1) entering.
"""
from __future__ import annotations
import random
from functools import lru_cache
from typing import List

INF = float("inf")


def calculate_minimum_hp_dp(dungeon: List[List[int]]) -> int:
    m, n = len(dungeon), len(dungeon[0])
    # dp[i][j] = min HP needed entering (i,j). Pad right/bottom with INF sentinels.
    dp = [[INF] * (n + 1) for _ in range(m + 1)]
    # INVARIANT: needed-after-goal = 1 (knight must finish with >=1 HP).
    dp[m][n - 1] = 1
    dp[m - 1][n] = 1
    for i in range(m - 1, -1, -1):
        for j in range(n - 1, -1, -1):
            need = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]
            dp[i][j] = max(1, need)
    return dp[0][0]


def calculate_minimum_hp_1d(dungeon: List[List[int]]) -> int:
    m, n = len(dungeon), len(dungeon[0])
    dp = [INF] * (n + 1)
    dp[n - 1] = 1  # so that bottom-right "after" successor reads as 1
    for i in range(m - 1, -1, -1):
        # INVARIANT: at row i, dp[j] for j=n still INF (right boundary); update last cell first.
        new_last = max(1, dp[n - 1] - dungeon[i][n - 1]) if i < m - 1 else max(1, 1 - dungeon[i][n - 1])
        # Simpler: rebuild row right-to-left with explicit handling.
        nxt = [INF] * (n + 1)
        for j in range(n - 1, -1, -1):
            if i == m - 1 and j == n - 1:
                successor = 1
            elif i == m - 1:
                successor = nxt[j + 1]
            elif j == n - 1:
                successor = dp[j]
            else:
                successor = min(dp[j], nxt[j + 1])
            nxt[j] = max(1, successor - dungeon[i][j])
        dp = nxt
        _ = new_last  # unused; kept for invariant clarity
    return dp[0]


def calculate_minimum_hp_memo(dungeon: List[List[int]]) -> int:
    m, n = len(dungeon), len(dungeon[0])

    @lru_cache(maxsize=None)
    def need(i: int, j: int) -> int:
        if i == m - 1 and j == n - 1:
            return max(1, 1 - dungeon[i][j])
        if i == m - 1:
            return max(1, need(i, j + 1) - dungeon[i][j])
        if j == n - 1:
            return max(1, need(i + 1, j) - dungeon[i][j])
        return max(1, min(need(i + 1, j), need(i, j + 1)) - dungeon[i][j])

    return need(0, 0)


def calculate_minimum_hp_brute(dungeon: List[List[int]]) -> int:
    # Enumerate all monotone paths; for each compute min starting HP; return overall min.
    m, n = len(dungeon), len(dungeon[0])
    best = INF

    def starting_hp_for_path(path_vals: List[int]) -> int:
        # HP after visiting cell k = s + sum(path_vals[:k+1]). Must be >= 1 for all k.
        # Also s >= 1 (knight must be alive entering cell 0).
        # s >= 1 - min(post-visit prefix sums).
        prefixes_after = []
        running = 0
        for v in path_vals:
            running += v
            prefixes_after.append(running)
        if not prefixes_after:
            return 1
        return max(1, 1 - min(prefixes_after))

    def dfs(i: int, j: int, vals: List[int]) -> None:
        nonlocal best
        vals.append(dungeon[i][j])
        if i == m - 1 and j == n - 1:
            best = min(best, starting_hp_for_path(vals))
        else:
            if i + 1 < m:
                dfs(i + 1, j, vals)
            if j + 1 < n:
                dfs(i, j + 1, vals)
        vals.pop()

    dfs(0, 0, [])
    return best


def edge_cases() -> None:
    d = [[-2, -3, 3], [-5, -10, 1], [10, 30, -5]]
    assert calculate_minimum_hp_dp(d) == 7
    assert calculate_minimum_hp_memo(d) == 7
    assert calculate_minimum_hp_brute(d) == 7
    assert calculate_minimum_hp_dp([[0]]) == 1
    assert calculate_minimum_hp_dp([[-3]]) == 4
    assert calculate_minimum_hp_dp([[100]]) == 1
    assert calculate_minimum_hp_dp([[1, -3, 3], [0, -2, 0], [-3, -3, -3]]) == 3
    print("edge_cases: PASS")


def stress_test() -> None:
    rng = random.Random(42)
    for trial in range(200):
        m = rng.randint(1, 4)
        n = rng.randint(1, 4)
        d = [[rng.randint(-10, 10) for _ in range(n)] for _ in range(m)]
        a = calculate_minimum_hp_dp(d)
        b = calculate_minimum_hp_1d(d)
        c = calculate_minimum_hp_memo(d)
        e = calculate_minimum_hp_brute(d)
        assert a == b == c == e, f"trial {trial}: d={d} dp={a} 1d={b} memo={c} brute={e}"
    print("stress_test: 200 trials — reverse DP, 1D, memoized, brute path-enum all agree.")


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