FastPrep
Problem · Matrix

Grid Infection with Recovery After D Days

Learn this problem
● MediumOpenAI logoOpenAIFULLTIMEPHONE SCREEN

Problem statement

Complete the function below. The function receives the full standard input as a single string and must return the exact standard output lines for the described problem.

Grid Infection with Recovery After D Days (Become Immune)

You are given a grid of cells. Each cell is in one of three states:

  • '.' — healthy (can be infected)
  • 'X' — infected
  • 'I' — immune (cannot be infected and does not infect others)

Each day, the following updates occur synchronously (all based on the state at the start of the day):

  • A healthy '.' cell becomes infected 'X' at the end of the day if it has at least T infected 'X' neighbors among its 8 neighbors (using the start-of-day state).
  • An infected 'X' cell that has been infected for exactly D days becomes immune 'I' at the end of that day. The infection age of a cell is incremented by 1 each day; a cell newly infected at the end of day k has age 1 after day k and recovers at the end of day k + D.
  • Immune 'I' cells never change state.

You must track the infection age of each cell. Return the number of days until the grid is stable, defined as: there are no infected 'X' cells remaining.

Input Format:

  • Line 1: two integers rows cols — the dimensions of the grid.
  • Line 2: two integers T D — the infection threshold and recovery duration.
  • Next rows lines: each line contains cols characters ('.', 'X', or 'I') representing the initial grid state. Any initially infected 'X' cell starts with infection age 1.

Output Format:

A single integer: the number of days until no 'X' cells remain.

Example Input:

3 3
1 1
.X.
...
...

Function

solveGridInfectionRecoveryAfterDays(input: String) → String[]

Examples

Example 1

input = "3 3\n1 1\n.X.\n...\n..."return = ["3"]
Simulating the 3x3 grid with T=1, D=1 synchronously: Initial state (age shown for X cells): 
. X(1) .
.  .   .
.  .   .
End of Day 1: (0,1) has age=1=D so it recovers to I. Meanwhile, all '.' cells adjacent to (0,1) — namely (0,0), (0,2), (1,0), (1,1), (1,2) — have at least 1 X neighbor, so they become X with age=1. 
X(1) I X(1)
X(1) X(1) X(1)
.    .    .
End of Day 2: The five X cells each have age=1=D, so they all recover to I. Meanwhile, (2,0), (2,1), (2,2) each have at least 1 X neighbor (from start-of-day state), so they become X with age=1. 
I I I
I I I
X(1) X(1) X(1)
End of Day 3: The three X cells in row 2 each have age=1=D, so they recover to I. No new X cells are created (no '.' cells remain). 
I I I
I I I
I I I
The grid is now stable with no X cells. The answer is 3.

Constraints

Constraints:

  • 1 ≤ rows, cols ≤ 100
  • 1 ≤ T ≤ 8
  • 1 ≤ D ≤ 100
  • The grid contains only characters '.', 'X', and 'I'.
  • The simulation is guaranteed to terminate (the grid will eventually have no 'X' cells).
  • All updates each day are synchronous: new states are computed from the start-of-day state and applied simultaneously at the end of the day.
  • Initially infected 'X' cells start with infection age 1.

More OpenAI problems

drafts saved locally
public String[] solveGridInfectionRecoveryAfterDays(String input) {
    // write your code here
}
input"3 3\n1 1\n.X.\n...\n..."
expected["3"]
checking account