【leetcode994】腐烂的橘子（BFS）

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

文章目录

一、题目
二、思路
三、代码

一、题目

在这里插入图片描述

二、思路

首先将所有烂橘子入队，然后常规BFS遍历，注意while的截止条件除了队列为空，新鲜橘子数量大于0（没新鲜橘子也没必要继续遍历，保证时间计算的正确性），这两者一个不满足就可以停止
每分钟进行一次【腐烂扩散】，使用BFS对二维图进行遍历，注意和二叉树的层次遍历不一样（二叉树则是只有一个根节点，这里可能有多个腐烂橘子-根节点）。
auto [x, y] = q.front()是C++17引入的新语法，结构化绑定，可以从数组、元组或结构体中一次性解包多个值，并将他们绑定到多个变量上，比如这里就是声明了x和y变量，然后将这2个变量绑定到元组中。如果不这么使用，可以直接通过first和second访问pair元素的数值。
auto& dir: directions是C++11的语法，&表示引用，直接auto dir则是按值访问，前者可以避免不必要的复制，并且允许你修改容器的容器。

三、代码

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}};int fresh_num = 0;//创建队列，存储腐烂的橘子二维坐标位置queue<pair<int, int>>q;for(int i=0; i < m;i++){for(int j=0; j < n; j++){if (grid[i][j] == 1)fresh_num += 1;//将所有烂橘子入队列if (grid[i][j] == 2)q.push({i, j});}}int minutes = 0;//烂橘子队列中没有橘子后则停止while(!q.empty() && fresh_num > 0){int q_num = q.size();//所有的烂橘子同时开始干活for(int i=0; i< q_num; i++){ //队首元素pair<int, int>one = q.front();q.pop(); //出队int x = one.first;int y = one.second;//遍历当前位置的上下左右for(auto& dir: directions){int nx = x + dir.first;int ny = y + dir.second;if(nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 1){ //如果是新鲜橘子grid[nx][ny] = 2;q.push({nx, ny});fresh_num -= 1;}}}minutes += 1;}return fresh_num == 0?minutes:-1;}
};