← 返回 openai 的题目列表Cellular Automata Infection Simulation
类型：online_judge
Problem: Cellular Automata Infection Simulation (Multi-part)
You are given a 2D grid grid of plants. Each cell is one of:
H: Healthy
I: Infected
X: Immune (never gets infected)
Adjacency uses 8 neighbors (including diagonals). Updates are synchronous: day d+1 depends only on day d.
Part 1 (Basic spread)
Given a threshold T: a healthy cell H becomes infected I the next day if it has at least T infected neighbors (cells in state I).
Compute the number of days until the outbreak ends:
The outbreak ends when, at the end of some day, all non-immune cells are infected.
Return the number of days from day 0 (initial state) to termination (minimum 0).
If it can never terminate, return -1.
Part 2 (Immune cells)
Same as Part 1, but the grid may contain immune cells X:
They never change to infected.
They occupy positions; neighbor counting still only counts infected neighbors I.
Termination condition remains: all non-immune cells are infected.
Part 3 (Recovery)
On top of Part 2, infected cells recover to healthy after C days of being infected.
If a cell becomes infected on day 2, it becomes healthy starting day 2 + C.
Recovery is also synchronous.
Now the termination condition is: at the end of some day, all non-immune cells are healthy H (i.e., no infections remain).
Return the number of days to reach termination, or -1 if impossible.
Suggested Input Format
Line 1: m n
Next m lines: strings of length n over H/I/X
Next line: integer T
Next line: integer mode in {1,2,3}
If mode = 3: one more integer C
Output
One integer: days or -1
Suggested Constraints
1 <= m, n <= 200
1 <= T <= 8
1 <= C <= 1e9
Sample Tests
input:
2 2
II
II
3
1
output:
0
input:
2 2
IH
HH
1
1
output:
1
input:
3 3
IHH
HXH
HHH
2
2
output:
-1
input:
2 3
IHH
HHH
1
2
output:
2
input:
1 3
IHH
1
3
1
output:
1
Example
Input
2 2
II
II
3
1
Output
0