-
Notifications
You must be signed in to change notification settings - Fork 3
/
994.cpp
42 lines (41 loc) · 1.32 KB
/
994.cpp
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
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
vector<pair<int, int>> directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
queue<pair<int, int>> q;
int freshCount = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 2) {
q.push(make_pair(i, j));
}
else if (grid[i][j] == 1) freshCount++;
}
}
int res = 0;
while (!q.empty()) {
int length = q.size();
int plus = 0;
while (length--) {
auto [x, y] = q.front();
q.pop();
for (auto direction : directions) {
int _x = x + direction.first;
int _y = y + direction.second;
if (_x < 0 || _x >= m || _y < 0 || _y >= n) continue;
if (grid[_x][_y] == 1) {
q.push(make_pair(_x, _y));
grid[_x][_y] = 2;
freshCount--;
plus++;
}
}
}
if (plus) res++;
}
if (freshCount > 0) return -1;
return res;
}
};