Virus Transmission
MediumGraph · Oracle
A lab grid is given as a list of equal-length strings. Each character is one cell:
'0': an infected cell (infected on day0).'1': a weak healthy cell.'2': a strong healthy cell.'_': an empty cell. Nothing lives there and infection cannot pass through it.
Infection spreads between cells that share a side (up, down, left, right). A cell is contagious from the day it becomes infected. A weak cell becomes infected 1 day after the first of its neighbours becomes infected; a strong cell becomes infected 2 days after the first of its neighbours becomes infected.
Return the day on which the last healthy cell becomes infected. Return 0 if there are no healthy cells, and -1 if some healthy cell can never be infected.
Example 1
- Input:
- grid = ["012", "_21"]
- Output:
- 4
- Explanation
- The weak cell next to the source falls on day 1. Both strong cells touch it, so they fall on day
1 + 2 = 3. The last weak cell in the bottom-right touches only those strong cells, so it falls on day3 + 1 = 4.
Example 2
- Input:
- grid = ["1_2", "0__"]
- Output:
- -1
- Explanation
- The weak cell above the source is infected on day 1, but the strong cell in the top-right corner touches only empty cells, so it can never be infected and the answer is
-1.
Example 3
- Input:
- grid = ["020", "111"]
- Output:
- 2
- Explanation
- The strong cell in the middle of the top row falls on day 2 from either side. The bottom row's weak cells fall on day 1 (corners) and day 2 (middle), so the last infection is on day 2.
Constraints
- 1 ≤ grid.length ≤ 100
- 1 ≤ grid[i].length ≤ 100, and all rows have the same length
- Each character is
'0','1','2'or'_'.