Virus Spread (Intuit India)

In the grid, 0 is empty land, 1 is a healthy cell, and 2 is an infected cell. Each second, the virus spreads only to healthy cells adjacent up, down, left, or right. Output the minimum number of seconds needed for all healthy cells to become infected; if some cell can never be infected, output -1.

输入格式

The input gives N M (1..100), followed by N lines of M integers (0..2).

输出格式

Output the answer as described; for array answers, separate values with spaces.

样例 1

输入：

3 3
2 1 1
1 1 1
1 1 2

输出：

2

样例 2

输入：

2 3
2 0 1
0 0 1

输出：

-1

样例 3

输入：

2 2
0 0
0 0

输出：

0

样例说明

Use all initially infected cells as BFS sources at the same time and infect healthy cells layer by layer.

Correctness: layer t of the multi-source BFS consists exactly of the cells that can be reached in a minimum of t seconds. The layer of the last healthy cell to be infected is the completion time; if healthy cells remain after the search ends, they are disconnected from all infected cells, so return -1. If there are no healthy cells, the answer is 0.

Complexity: O(NM) time, O(NM) space.