## Spreading Contagion on a Grid You are given an `m x n` integer grid `cells`. Each entry has one of three values: - `0` — an empty location (no unit present). - `1` — a **healthy** unit. - `2` — an **infected** unit. Time advances in discrete **minutes**. Every minute, any healthy unit (`1`) that is **4-directionally adjacent** (up, down, left, right) to an infected unit (`2`) becomes infected. All infections that can happen in a given minute happen simultaneously. This problem has three independent parts. Each part is self-contained and uses the same grid encoding; solve all three. --- ### Part 1 — Time to full infection Return the **minimum number of minutes** that must elapse until **no healthy unit** remains. If it is impossible for every healthy unit to become infected (some healthy unit can never be reached by the contagion), return `-1`. **Function signature** ```python def minutes_to_infect(cells: list[list[int]]) -> int: ... ``` **Example** ```text Input: cells = [[2,1,1], [1,1,0], [0,1,1]] Output: 4 ``` ```text Input: cells = [[2,1,1], [0,1,1], [1,0,1]] Output: -1 Explanation: The healthy unit in the bottom-left corner is never reached, because infection only spreads 4-directionally. ``` ```text Input: cells = [[0,2]] Output: 0 Explanation: There are already no healthy units at minute 0. ``` --- ### Part 2 — Identify the immune units Some healthy units can **never** become infected no matter how much time passes (they are unreachable from every initial infection source). Call such a unit **immune**. Return the **count of immune units** in the grid (healthy units that the contagion can never reach). Empty locations (`0`) and infected locations (`2`) are not units and must not be counted. **Function signature** ```python def count_immune(cells: list[list[int]]) -> int: ... ``` **Example** ```text Input: cells = [[2,1,1], [0,1,1], [1,0,1]] Output: 1 Explanation: The bottom-left healthy unit is isolated from the contagion and is the only immune unit. ``` --- ### Part 3 — Time-limited immunity (dynamic) Now immunity is acquired **dynamically over time**. You are given an additional integer `x`. A unit develops **lasting immunity** if it survives — i.e. stays healthy — for at least `x` consecutive minutes from the start. Concretely: - A healthy unit that has **not yet been infected** by the end of minute `x - 1` (equivalently, a unit that is still healthy strictly after `x` minutes of spreading have been applied) becomes **permanently immune** and can **never** be infected afterward, even if an infected neighbor later appears next to it. - Infections in minutes `1` through `x` still proceed normally on units that are not yet immune. Because immunity is granted **at the same instant** that the contagion is still racing across the grid, a unit being infected in minute `x` versus becoming immune at minute `x` is a tie that must be resolved deterministically: **infection that lands at minute `x` takes effect; immunity is granted only to units that are still healthy after minute `x`'s infections are applied.** Return the **number of units that are still healthy once the system reaches a steady state** (no further infections are possible). This count includes both units that became permanently immune at minute `x` and units that were never reachable at all. **Function signature** ```python def survivors_with_immunity(cells: list[list[int]], x: int) -> int: ... ``` **Examples** ```text Input: cells = [[2,1,1,1,1]], x = 2 Output: 2 Explanation: Minute 0: [2,1,1,1,1] Minute 1: [2,2,1,1,1] Minute 2: [2,2,2,1,1] <- after minute x=2's infections are applied, the two rightmost units are still healthy and become permanently immune. Steady state: those 2 immune units remain healthy forever. Answer = 2. ``` ```text Input: cells = [[2,1,1]], x = 5 Output: 0 Explanation: The whole row is infected within 2 minutes, which is before minute x=5, so no unit survives long enough to gain immunity. ``` ```text Input: cells = [[2,1], [0,1]], x = 1 Output: 1 Explanation: Minute 1: the top-right unit is infected; the bottom-right unit is not adjacent to any infected unit yet, so it is still healthy after minute 1 and becomes permanently immune. Answer = 1. ``` ### Constraints - `1 <= m, n` and `m * n <= 10^4`. - Each `cells[i][j]` is `0`, `1`, or `2`. - For Part 3, `0 <= x <= m * n`. When `x == 0`, every healthy unit is immune from the start and the answer is the total count of healthy units. - Note for Part 3: the dynamic immunity rule means a simple multi-source BFS that floods to completion is **not** sufficient — immunity must be applied at the correct time boundary, after which newly-arriving infection can no longer overwrite an immune unit.