0%

题目描述

In a given grid, each cell can have one of three values:

the value `0` representing an empty cell;
the value `1` representing a fresh orange;
the value `2` representing a rotten orange.
Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return `-1` instead.

例子

例子 1

Input: `[[2,1,1],[1,1,0],[0,1,1]]`
Output: 4

例子 2

Input: `[[2,1,1],[0,1,1],[1,0,1]]`
Output: -1
Explaination：The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

例子 3

Input: `[[0,2]]`
Output: 0
Explaination：Since there are already no fresh oranges at minute 0, the answer is just 0.

Note

• `1 <= grid.length <= 10`
• `1 <= grid[0].length <= 10`
• `grid[i][j]` is only `0`, `1`, or `2`.

解题思路

方法一

• 时间复杂度: O(n^4) 时间复杂度不太确定，但是每次进行 `bfs` 都有可能会重复遍历之前遍历过的位置，所以复杂度肯定在 O(n^2) 以上
• 空间复杂度: O(n^2)

方法二

• 时间复杂度: O(n^2)
• 空间复杂度: O(n^2)