本文主要是介绍NC398 腐烂的苹果，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
腐烂的苹果
一个腐烂的苹果每分钟可以向上下左右四个方向扩展，扩展之后，又会有新的腐烂的苹果，一直去腐蚀好的苹果，求多少分钟后，网格中全是烂苹果。
第一次做这道题的时候，想到这道题考察的其实是多源BFS的知识点了。
多源BFS
把所有的源点当成一个超级源点。问题就变成了单一的单源最短路问题
将所有腐烂的苹果全部放到一个队列里面，然后层层的向外扩展，每次扩展都要把队列里面所有的烂苹果给pop出去。bfs搜索会把一个烂苹果周围的好苹果放入到队列里面，因为每分钟烂苹果都要向外扩展一次，所以队列里面的烂苹果向外扩展耗费的时间是同一分钟。
class Solution {public:int n, m;int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};queue<pair<int, int>> q;int rotApple(vector<vector<int> >& g) {// write code heren = g.size();m = g[0].size();// 将所有烂苹果当成一个大的烂苹果for (int i = 0; i < n; i ++) {for (int j = 0; j < m; j++) {if (g[i][j] == 2) {q.push({i, j});}}}// 记录耗费的时间int ret = 0;while (!q.empty()) {// 每次扩展都要将队列清空int sz = q.size();ret++;while (sz--) {auto [i, j] = q.front();q.pop();for (int t = 0; t < 4; t++) {int x = i + dx[t];int y = j + dy[t];if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 1) {// 遍历过的苹果不能在遍历到了，可以搞一个bool数组，也可以在原数组上进行修改g[x][y] = 2;// 好苹果加入到队列当中q.push({x, y});}}}}// 判断是否有苹果不能被腐蚀for (int i = 0; i < n; i++) for (int j = 0; j < m; j++)if (g[i][j] == 1)return -1;return ret - 1;}
};这篇关于NC398 腐烂的苹果的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
