← 返回 openai 的题目列表Infection Spread with Immune Units and Expiring Contagiousness
类型：online_judge
Problem: Infection Spread with Immune Units
You are given an m x n grid. Each cell represents a unit:
0: empty/blocked cell, not involved in infection and cannot be infected;
1: healthy susceptible unit;
2: infected unit;
3: immune unit, cannot be infected and does not spread infection.
The infection spreads by days:
Each day, every unit that is still contagious infects its four adjacent healthy neighbors;
Newly infected units can start spreading infection from the next day;
A unit becomes immune x days after it is infected, and after that it no longer spreads infection;
Immune units and empty cells cannot be infected.
Return the minimum number of days needed until every infectable healthy unit has been infected.
If some healthy units can never be infected, return -1.
Input Format
The first line contains three integers:
m n x
The next m lines each contain n integers representing the grid.
Output Format
Print one integer: the minimum number of days needed to infect all susceptible units, or -1 if impossible.
Constraints
1 <= m, n <= 500
0 <= x <= 10^9
grid[i][j] ∈ {0, 1, 2, 3}
Example 1
Input:
3 3 2
2 1 1
1 1 0
0 1 1
Output:
4
Example 2
Input:
3 3 2
2 1 1
0 1 1
1 0 1
Output:
-1
Explanation: the healthy unit in the bottom-left corner is separated by blocked cells and cannot be infected.
Example 3
Input:
2 3 1
2 3 1
1 1 1
Output:
3
Explanation: immune units cannot be infected, but infection can still spread through other paths.
Example
Input
3 3 2
2 1 1
1 1 0
0 1 1
Output
4