Infection Spread Simulation

MEDIUM20 pts

You are given an m × n grid representing a population region where each cell can be in one of three states:

0 represents an empty cell (no population present)
1 represents a healthy individual
2 represents an infected individual

The infection spreads according to a simple epidemic model: every minute, any healthy individual that is directly adjacent (up, down, left, or right—not diagonal) to an infected individual becomes infected.

Your task is to determine the minimum number of minutes required for the infection to spread to all healthy individuals in the grid. If it is impossible for all healthy individuals to become infected (due to isolation by empty cells or other barriers), return -1.

Key Observations:

Multiple infected individuals can spread the infection simultaneously
The infection spreads in parallel from all currently infected cells at each time step
Empty cells act as barriers that the infection cannot cross
The answer is 0 if there are no healthy individuals initially

Example

Input

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

Output

4

Explanation

The infection originates from the top-left cell (0,0). At minute 1, cells (0,1) and (1,0) become infected. At minute 2, cells (0,2) and (1,1) become infected. At minute 3, cell (2,1) becomes infected. At minute 4, cell (2,2) becomes infected. Total time: 4 minutes.

Example

Input

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

Output

-1

Explanation

The healthy individual in the bottom-left cell (2,0) is completely isolated from all infected cells by empty cells. Infection can only spread horizontally or vertically through adjacent healthy cells, so this individual can never be reached. Therefore, complete infection is impossible.

Example

Input

grid = [[0,2]]

Output

0

Explanation

There are no healthy individuals in the grid at the start. The only non-empty cell is already infected. Therefore, zero time is needed for the infection to spread to all healthy individuals (since there are none).

Accepted0/0·0% Acceptance

Constraints

m == grid.length
n == grid[i].length
1 ≤ m, n ≤ 10
grid[i][j] is 0, 1, or 2

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

grid =

[[2,1,1],[1,1,0],[0,1,1]]

Infection Spread Simulation

Hints

Infection Spread Simulation

Hints