1302 - 腐烂的橘子

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

  • 0 代表空单元格;

  • 1 代表新鲜橘子;

  • 2 代表腐烂的橘子。

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

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

输入

第一行为2个整数m,n,表示grid的行和列

以下m行n列为grid的具体内容

输出

直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能,输出 -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

提示

  • m == grid.length

  • n == grid[i].length

  • 1 <= m, n <= 10

  • grid[i][j] 仅为 012

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题