Day 6:994 腐烂的橘子

本文主要是介绍Day 6:994 腐烂的橘子，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 题目描述

994 腐烂的橘子

2. 解题思路

(1) 首先统计新鲜橘子的数量并将腐烂橘子坐标加入初始队列中；
(2) 使用BFS遍历的思想依次遍历每一层，首先判断是否存在新鲜橘子，若存在则时间+1；
(3) 对于每一层若遇到新鲜橘子则将其变为腐烂橘子并加入队列中，同时新鲜橘子数-1；
(4) 返回所需时间值。

3. 代码实现（广度优先遍历）

class Solution {static constexpr int dirs[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};public:// bfs的思想int orangesRotting(vector<vector<int>>& grid) {int m = grid.size();int n = grid[0].size();// 用以存储腐烂橘子queue<pair<int, int>> que;// 表示新鲜橘子的个数int cnt_fresh = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == 1) {cnt_fresh++;} else if (grid[i][j] == 2) {que.push({i, j});}}}int time = 0;while (!que.empty()) {int sz = que.size();// 判断是否存在新鲜橘子if (cnt_fresh != 0)time++;for (int k = 0; k < sz; k++) {auto [i, j] = que.front();que.pop();for (auto [dir_x, dir_y] : dirs) {int x = dir_x + i;int y = dir_y + j;if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {grid[x][y] = 2;que.push({x, y});cnt_fresh--;}}}}return cnt_fresh ? -1 : time;}
};

这篇关于Day 6:994 腐烂的橘子的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---