You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

• 值 0 代表空单元格；
• 值 1 代表新鲜橘子；
• 值 2 代表腐烂的橘子。

每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

输入

第一行输入m, n，

接下来 m 行，每行输入一个整数，表示单元格的状态。

输出

输出一行，一个整数，表示单元格中没有新鲜橘子所经过的最小分钟数，或 -1。

样例

3 3
2 1 1
1 1 0
0 1 1

4

3 3
2 1 1
0 1 1
1 0 1

-1

1 2
0 2

0

提示

【样例1解释】

【数据范围】

1 ≤ m, n ≤ 10

grid[i][j] 仅为0、1 或 2

​