Simulate Infection Spread with Immunity and Recovery

Problem Statement

You are given an m x n grid representing a population layout and two integers: recovery_time and days.

Each cell in the grid contains one of the following characters:

• 'S': Susceptible individual (can be infected).
• 'I': Newly infected individual (infection counter starts at recovery_time).
• 'M': Naturally immune individual (cannot be infected).
• 'R': Recovered individual (cannot be infected).
• 'E': Empty space (cannot be infected).

The simulation advances day by day in discrete, synchronous steps. Each day, the following events occur simultaneously:

1. Spread: Every cell that was infected at the start of the day attempts to spread the infection to its 4-directionally adjacent (up, down, left, right) neighbors. Any neighbor that is 'S' becomes infected for the next day with an infection counter set to recovery_time.
2. Progression and Recovery: Every cell that was infected at the start of the day decrements its remaining infection counter by 1. If its counter reaches 0 at the end of the day, it recovers and transitions to state 'R'.

All individuals infected in the initial input grid are assumed to have just been infected, meaning they have recovery_time days remaining.

Simulate the spread for days days and return the final state of the grid as a 2D list of characters.

Function Signature

def simulate_infection(grid: list[list[str]], recovery_time: int, days: int) -> list[list[str]]:
    pass

Constraints

• 1 <= m, n <= 50
• grid[r][c] is one of {'S', 'I', 'M', 'R', 'E'}
• 1 <= recovery_time <= 100
• 0 <= days <= 1000

Examples

Example 1

Input:
grid = [
    ["I", "S", "E"],
    ["S", "M", "S"],
    ["E", "S", "S"]
]
recovery_time = 2
days = 2

Output:
[
    ["R", "I", "E"],
    ["I", "M", "S"],
    ["E", "S", "S"]
]

Explanation:

• Day 0 (Initial): (0, 0) is 'I' with 2 days left.
• Day 1: (0, 0) spreads to (0, 1) and (1, 0). (0, 0) has 1 day left. (0, 1) and (1, 0) become 'I' with 2 days left.
• Day 2: (0, 0) counter reaches 0 -> becomes 'R'. (0, 1) and (1, 0) decrement to 1 day left, and neither infects any new susceptible neighbors because (1, 1) is 'M' and (0, 2) / (2, 0) are 'E'.

Example 2

Input:
grid = [
    ["I", "S"],
    ["S", "S"]
]
recovery_time = 1
days = 1

Output:
[
    ["R", "I"],
    ["I", "S"]
]

Explanation:

• Day 1: (0, 0) infects (0, 1) and (1, 0). Since recovery_time = 1, (0, 0) decrements to 0 and becomes 'R'. Newly infected cells become 'I'.