## Infection Spread on a Grid (Cellular Automaton) You are simulating how an infection spreads across a 2D grid of cells over a sequence of discrete time steps. The grid is a rectangular matrix with `R` rows and `C` columns. Each cell is in exactly one of these states: - `H` — healthy (susceptible) - `I` — infected - `R` — recovered/removed (immune; can never be infected again) - `W` — wall/empty (a permanent barrier; never changes state and does not transmit infection) Time advances in **discrete steps**. At each step, every cell is updated **simultaneously** based on the configuration at the **start** of that step (a classic synchronous cellular-automaton update — a cell that becomes infected during a step does not infect its neighbors until the *next* step). Two cells are **neighbors** if they are orthogonally adjacent (up, down, left, right). Diagonal cells are **not** neighbors. Implement the simulation in the parts below. Each part builds on the previous one. --- ### Part 1 — One step of basic spread Given the grid, compute the grid after exactly **one** step under this rule: - A `H` (healthy) cell becomes `I` (infected) in the next step if **at least one** of its orthogonal neighbors is `I` at the start of the step. - `I`, `R`, and `W` cells keep their state. Updates are simultaneous. Return the resulting grid. **Example** ``` Start: After 1 step: H H H H I H H I H ---> I I I H H H H I H ``` --- ### Part 2 — Simulate `k` steps Generalize Part 1 to run the simulation for `k` steps (`k >= 0`) and return the grid after the `k`-th step. With `k = 0` the grid is returned unchanged. Walls (`W`) continue to block spread (infection cannot pass through or into a wall), and recovered (`R`) cells remain immune. **Example** ``` Start: k = 2 H H H H H H I W H H H H W H H H H H H H After 2 steps: I I I H H I I W H H I I W H H H I H H H ``` (The wall column blocks the infection from crossing directly through it; the infection must travel around.) --- ### Part 3 — Infection with a recovery delay Now infected cells recover. Each cell carries a **time-since-infection** counter. The rules per step (applied simultaneously) are: - A `H` cell with at least one `I` neighbor becomes `I` next step, with its infection counter set to `1`. - An `I` cell that has been infected for fewer than `d` steps stays `I` and increments its counter. - An `I` cell that has been infected for exactly `d` steps becomes `R` (recovered) next step. Recovered cells are immune forever and never become infected again. - `R` and `W` cells never change. Here `d >= 1` is the **infectious duration**. (When `d` is effectively infinite, this reduces to Part 2.) Run the simulation for `k` steps and return the final grid (each cell as `H`, `I`, `R`, or `W`). **Example** ``` d = 1, k = 2 Start: After 1 step: After 2 steps: H H H H I H I R I H I H ---> I R I ---> R R R H H H H I H I R I ``` (With `d = 1`, a cell infected at one step recovers at the very next step, but it still infects its healthy neighbors during the step in which it is infected.) --- ### Part 4 — Stop early when the grid stabilizes Combine all earlier rules (spread with infectious duration `d`, walls, permanent immunity). The simulation may be requested to run up to `k` steps, but you must **stop early** as soon as the grid reaches a state in which **no cell can change in any subsequent step** — i.e., a fixed point: there is no `H` cell adjacent to an `I` cell, and there is no `I` cell remaining (every infection has either spread out or recovered). Return a pair: the final grid **and** the number of steps actually simulated. If the grid is already stable at the start, return it with `0` steps. If it never stabilizes within `k` steps, return the grid after `k` steps along with `k`. Be precise about the stopping condition: the grid is stable only when **no further transition is possible** — both "no new infections can occur" **and** "no infected cell is still mid-recovery." A grid that still contains an `I` cell which will recover next step is **not** yet stable, even if no healthy cell is adjacent to an infection. **Example** ``` d = 2, k = 100 Start: H H H H I H H H H The infection spreads outward, every infected cell eventually recovers, and once the whole reachable region is R (and no I remains) no further change is possible. Return that final all-recovered grid together with the exact number of steps taken to reach it (which is far fewer than 100). ``` --- ### Input / Output - **Input**: the grid as a list of strings (or a 2D array of characters) over the alphabet `{H, I, R, W}`; integers `k` and (for Parts 3–4) `d`. - **Output**: - Parts 1–3: the resulting grid in the same format. - Part 4: the resulting grid **and** the integer count of steps actually simulated. ### Constraints - `1 <= R, C <= 1000`; `1 <= R * C <= 10^6`. - `0 <= k <= 10^6`. - `1 <= d <= 10^6`. - The input grid contains only the characters `H`, `I`, `R`, `W`. - Aim for an approach whose total work scales with the number of cells and the spread, rather than re-scanning the entire grid for every one of up to `k` steps when most of the grid is inert.