本文主要是介绍【题解】NC398 腐烂的苹果(多源BFS)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
https://www.nowcoder.com/practice/54ab9865ce7a45968b126d6968a77f34?tpId=196&tqId=40529&ru=/exam/oj
从每个腐烂的苹果开始使用广度优先遍历（bfs）
class Solution {int n, m;int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};vector<vector<bool>> vis;public:int rotApple(vector<vector<int> >& grid) {// write code herem = grid.size(), n = grid[0].size();vis.assign(m, vector<bool>(n, false));// 将腐烂苹果放进queuequeue<pair<int, int>> q;for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (grid[i][j] == 2) {q.push({i, j});}}}int ret = 0;// 一层一层的遍历，广度优先遍历while (q.size()) {int sz = q.size();ret++;while (sz--) {auto [a, b] = q.front();q.pop();for (int k = 0; k < 4; ++k) {int x = a + dx[k];int y = b + dy[k];if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] == 1) {vis[x][y] = true;q.push({x, y});}}}}// 判断是否有永不腐烂的苹果for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (grid[i][j] == 1 && !vis[i][j]) {return -1;}}}return ret - 1;}
};
这篇关于【题解】NC398 腐烂的苹果(多源BFS)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
