← 返回 openai 的题目列表2D Grid Infection (BFS Spread)
类型：online_judge
Coding: 2D Grid Infection Spread
You are given an m x n matrix grid representing an infection process:
0 = empty cell
1 = uninfected
2 = infected
Every minute, infected cells infect their 4-directionally adjacent uninfected neighbors.
Return the minimum number of minutes required to infect all uninfected cells. If it’s impossible, return -1.
Input (stdin)
Line 1: two integers m n
Next m lines: n integers each representing grid[i][j]
Output (stdout)
One integer: the minimum minutes or -1
Constraints
1 <= m, n <= 200
grid[i][j] ∈ {0,1,2}
Example
Input:
3 3
2 1 1
1 1 0
0 1 1
Output:
4
Example
Input
3 3
2 1 1
1 1 0
0 1 1
Output
4