← 返回 openai 的题目列表Minimum Time to Infect All Plants
类型：online_judge
Problem: Plant Infection
You are given an m x n grid representing an area of plants. Each cell has one of the following values:
0: empty land, no plant.
1: healthy plant.
2: infected plant.
Every minute, all currently infected plants simultaneously infect their four-directionally adjacent healthy plants: up, down, left, and right.
Return the minimum number of minutes required to infect all healthy plants. If some healthy plant can never be infected, return -1.
Input Format
The first line contains two integers m and n.
The next m lines each contain n integers representing the grid.
Output Format
Print one integer: the minimum number of minutes required to infect all healthy plants, or -1 if impossible.
Constraints
1 <= m, n <= 500
grid[i][j] is one of 0, 1, or 2
The total number of cells is at most 2 * 10^5
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