题目描述
在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
- 值
0 代表空单元格；
- 值
1 代表新鲜橘子；
- 值
2 代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
示例 1：
输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
输出：4
示例 2：
输入：grid = [[2,1,1],[0,1,1],[1,0,1]]
输出：-1
解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个方向上。
示例 3：
输入：grid = [[0,2]]
输出：0
解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 10grid[i][j] 仅为 0、1 或 2
解法
方法一：BFS
我们首先遍历一遍整个网格，统计出新鲜橘子的数量，记为 $\textit{cnt}$，并且将所有腐烂的橘子的坐标加入队列 $q$ 中。
接下来，我们进行广度优先搜索，每一轮搜索，我们将队列中的所有腐烂的橘子向四个方向腐烂新鲜橘子，直到队列为空或者新鲜橘子的数量为 $0$ 为止。
最后，如果新鲜橘子的数量为 $0$，则返回当前的轮数，否则返回 $-1$。
时间复杂度 $O(m \times n)$，空间复杂度 $O(m \times n)$。其中 $m$ 和 $n$ 分别是网格的行数和列数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
q = deque()
cnt = 0
for i, row in enumerate(grid):
for j, x in enumerate(row):
if x == 1:
cnt += 1
elif x == 2:
q.append((i, j))
dirs = (-1, 0, 1, 0, -1)
ans = 0
while q and cnt:
ans += 1
for _ in range(len(q)):
i, j = q.popleft()
for a, b in pairwise(dirs):
x, y = i + a, j + b
if 0 <= x < m and 0 <= y < n and grid[x][y] == 1:
grid[x][y] = 2
q.append((x, y))
cnt -= 1
return -1 if cnt > 0 else ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32 | class Solution {
public int orangesRotting(int[][] grid) {
int m = grid.length, n = grid[0].length;
Deque<int[]> q = new ArrayDeque<>();
int cnt = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 1) {
++cnt;
} else if (grid[i][j] == 2) {
q.offer(new int[] {i, j});
}
}
}
final int[] dirs = {-1, 0, 1, 0, -1};
int ans = 0;
for (; !q.isEmpty() && cnt > 0; ++ans) {
for (int k = q.size(); k > 0; --k) {
var p = q.poll();
for (int d = 0; d < 4; ++d) {
int x = p[0] + dirs[d], y = p[1] + dirs[d + 1];
if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {
grid[x][y] = 2;
q.offer(new int[] {x, y});
--cnt;
}
}
}
}
return cnt > 0 ? -1 : ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34 | class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
queue<pair<int, int>> q;
int cnt = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 1) {
++cnt;
} else if (grid[i][j] == 2) {
q.emplace(i, j);
}
}
}
int ans = 0;
const int dirs[5] = {-1, 0, 1, 0, -1};
for (; q.size() && cnt; ++ans) {
for (int k = q.size(); k; --k) {
auto [i, j] = q.front();
q.pop();
for (int d = 0; d < 4; ++d) {
int x = i + dirs[d], y = j + dirs[d + 1];
if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {
grid[x][y] = 2;
q.emplace(x, y);
--cnt;
}
}
}
}
return cnt > 0 ? -1 : ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 | func orangesRotting(grid [][]int) (ans int) {
m, n := len(grid), len(grid[0])
q := [][2]int{}
cnt := 0
for i, row := range grid {
for j, x := range row {
if x == 1 {
cnt++
} else if x == 2 {
q = append(q, [2]int{i, j})
}
}
}
dirs := [5]int{-1, 0, 1, 0, -1}
for ; len(q) > 0 && cnt > 0; ans++ {
for k := len(q); k > 0; k-- {
p := q[0]
q = q[1:]
for d := 0; d < 4; d++ {
x, y := p[0]+dirs[d], p[1]+dirs[d+1]
if x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 {
grid[x][y] = 2
q = append(q, [2]int{x, y})
cnt--
}
}
}
}
if cnt > 0 {
return -1
}
return
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32 | function orangesRotting(grid: number[][]): number {
const m: number = grid.length;
const n: number = grid[0].length;
const q: number[][] = [];
let cnt: number = 0;
for (let i: number = 0; i < m; ++i) {
for (let j: number = 0; j < n; ++j) {
if (grid[i][j] === 1) {
cnt++;
} else if (grid[i][j] === 2) {
q.push([i, j]);
}
}
}
let ans: number = 0;
const dirs: number[] = [-1, 0, 1, 0, -1];
for (; q.length && cnt; ++ans) {
const t: number[][] = [];
for (const [i, j] of q) {
for (let d = 0; d < 4; ++d) {
const [x, y] = [i + dirs[d], j + dirs[d + 1]];
if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] === 1) {
grid[x][y] = 2;
t.push([x, y]);
cnt--;
}
}
}
q.splice(0, q.length, ...t);
}
return cnt > 0 ? -1 : ans;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51 | use std::collections::VecDeque;
impl Solution {
pub fn oranges_rotting(mut grid: Vec<Vec<i32>>) -> i32 {
let m = grid.len();
let n = grid[0].len();
let mut q = VecDeque::new();
let mut cnt = 0;
for i in 0..m {
for j in 0..n {
if grid[i][j] == 1 {
cnt += 1;
} else if grid[i][j] == 2 {
q.push_back(vec![i as i32, j as i32]);
}
}
}
let dirs: [i32; 5] = [-1, 0, 1, 0, -1];
let mut ans = 0;
while !q.is_empty() && cnt > 0 {
let q_size = q.len();
for _ in 0..q_size {
let p = q.pop_front().unwrap();
for d in 0..4 {
let x = p[0] + dirs[d];
let y = p[1] + dirs[d + 1];
if x >= 0
&& x < (m as i32)
&& y >= 0
&& y < (n as i32)
&& grid[x as usize][y as usize] == 1
{
grid[x as usize][y as usize] = 2;
q.push_back(vec![x, y]);
cnt -= 1;
}
}
}
ans += 1;
}
if cnt > 0 {
return -1;
}
ans
}
}
|