題目描述：994. 腐爛的橘子 - 力扣（LeetCode）
腐爛的橘子會污染周圍的橘子，要求多少輪擴(kuò)散才能把全部橘子污染，這就相當(dāng)于滴墨水入清水，會擴(kuò)散，其實就是廣度遍歷，看看遍歷多少層可以遍歷完可以遍歷的
先遍歷一次橘子，記錄下腐爛橘子的位置和新鮮橘子的數(shù)目，然后廣度遍歷腐爛橘子并向外擴(kuò)散污染新鮮橘子文章來源：http://www.zghlxwxcb.cn/news/detail-856593.html
注意向外擴(kuò)散時需要每次取位置，因為移動會改變位置，位置需要重置文章來源地址http://www.zghlxwxcb.cn/news/detail-856593.html
class Solution {
public:
int rows, columns;
vector<vector<int> > grid;
bool isValid(int x, int y) {
return x >= 0 && y >= 0 && x < rows && y < columns;
}
int orangesRotting(vector<vector<int> > &grid) {
rows = grid.size();
columns = grid[0].size();
this->grid = move(grid);
int ans = 0, fresh = 0;
queue<pair<int, int> > pullte;
for (int i = 0; i < rows; ++i)
for (int j = 0; j < columns; ++j)
if (this->grid[i][j] == 1)
++fresh;
else if (this->grid[i][j] == 2)
pullte.emplace(i, j);
int move[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
while (fresh > 0 && !pullte.empty()) {
int scale = pullte.size();
while (--scale >= 0) {
for (int i = 0; i < 4; ++i) {
auto [x,y] = pullte.front();
x += move[i][0];
y += move[i][1];
if (isValid(x, y) && this->grid[x][y] == 1) {
this->grid[x][y] = 2;
pullte.emplace(x, y);
--fresh;
}
}
pullte.pop();
}
++ans;
}
if (fresh > 0)
return -1;
return ans;
}
};到了這里，關(guān)于【LeetCode熱題100】【圖論】腐爛的橘子的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
