FastPrep
Problem · Matrix

Infection Spread / Cellular Automata

Learn this problem
● MediumOpenAI logoOpenAIFULLTIMEPHONE SCREEN

Problem statement

You are given a two-dimensional grid that models an infection process. Each cell has one of three values:

  • 0: healthy
  • 1: infected
  • 2: immune

Each day, every currently infected cell simultaneously infects its 4-directional healthy neighbors. Cells infected today can only start spreading the infection tomorrow. Immune cells never become infected and never spread the infection.

Return the number of days needed until every non-immune healthy cell is infected. If there is no initial infected cell, or if any healthy cell can never be reached because of immune cells, return -1. If every non-immune cell is already infected, return 0.

Function

timeToFullInfectionWithImmunity(grid: int[][]) → int

Examples

Example 1

grid = [[1, 0, 0], [0, 2, 0], [0, 0, 0]]return = 4

The infection spreads around the immune center cell. The farthest healthy cell becomes infected after 4 days.

Example 2

grid = [[1, 2, 0], [2, 0, 0], [0, 0, 0]]return = -1

The initial infected cell is blocked by immune cells, so the remaining healthy cells can never be infected.

Example 3

grid = [[1, 2], [2, 1]]return = 0

There are no healthy non-immune cells to infect.

Constraints

  • grid is a rectangular matrix.
  • Each cell is 0, 1, or 2.
  • Infection spreads only in the four orthogonal directions.

More OpenAI problems

drafts saved locally
public int timeToFullInfectionWithImmunity(int[][] grid) {
  // write your code here
}
grid[[1, 0, 0], [0, 2, 0], [0, 0, 0]]
expected4
checking account