Leetcode 994. Rotting Oranges(BFS)


题目来源:https://leetcode.com/problems/cousins-in-binary-tree/description/

标记难度:Easy

提交次数:1/1

代码效率:12ms

题意

在一个四连通图上有若干个橘子,其中有一些是烂的,烂橘子每秒都会向四连通的橘子扩散,问经过多少秒,所有的橘子会烂掉?

分析

前几天在CF上做过一道有点类似的题(1105D,也是BFS分次扩展,当时虽然过了pretest,却因为每次扩展的结点过多且queue初始化过慢超时了。所以我就学到了一个道理:在这种情况下注意到底应该扩展哪些结点。不过这道题其实没有这个必要……

考虑到这一点,不如直接用vector代替queue

代码

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
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
vector<pair<int, int>> q;
int orangeCnt = 0;
int n = grid.size(), m = grid[0].size();
int mx[4] = {0, 0, 1, -1};
int my[4] = {1, -1, 0, 0};

for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] != 0) orangeCnt++;
if (grid[i][j] == 2) q.emplace_back(i, j);
}
}

if (q.size() == orangeCnt) return 0; // 全都烂了
if (q.size() == 0) return -1; // 根本没有烂的
// [lastEnd, lastSize)这部分是本次需要扩展的
// 之前的已经扩展过了,没有再扩展一次的必要
int lastEnd = 0, lastSize = q.size();
for (int i = 1; ; i++) {
for (int j = lastEnd; j < lastSize; j++) {
int x = q[j].first, y = q[j].second;
for (int k = 0; k < 4; k++) {
int nx = x + mx[k], ny = y + my[k];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (grid[nx][ny] == 1) {
grid[nx][ny] = 2;
q.emplace_back(nx, ny);
}
}
}
// 本次没有扩展出新的烂橘子,且还有橘子没烂,说明扩展不到那边了
if (lastSize == q.size()) return -1;
// 所有橘子都烂了
if (q.size() == orangeCnt) return i;
lastEnd = lastSize;
lastSize = q.size();
}
return 0;
}
};

 评论