力扣994. 腐烂的橘子

题目腐烂的橘子https://leetcode.cn/problems/rotting-oranges/description/在给定的m x n网格grid中每个单元格可以有以下三个值之一0代表空单元格1代表新鲜橘子2代表腐烂的橘子。每分钟腐烂的橘子周围 4 个方向上相邻的新鲜橘子都会腐烂。返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能返回-1。示例 1输入grid [[2,1,1],[1,1,0],[0,1,1]] 输出4示例 2输入grid [[2,1,1],[0,1,1],[1,0,1]] 输出-1 解释左下角的橘子第 2 行第 0 列永远不会腐烂因为腐烂只会发生在 4 个方向上。示例 3输入grid [[0,2]] 输出0 解释因为 0 分钟时已经没有新鲜橘子了所以答案就是 0。提示m grid.lengthn grid[i].length1 m, n 10grid[i][j]仅为0、1或2解法多源 BFS广度优先搜索思路将所有初始腐烂的橘子作为 BFS 的起点同时入队并记录它们的位置和时间时间为 0。同时统计新鲜橘子的数量fresh。然后开始 BFS 过程每次从队列中取出一个腐烂橘子检查其四个方向若遇到新鲜橘子则将其腐烂值改为 2新鲜橘子计数减 1并将该橘子入队时间1。BFS 结束后如果fresh 0则返回最后的时间即所有橘子腐烂所需的最大分钟数否则返回 -1。复杂度时间复杂度O(m × n)每个单元格最多入队一次。空间复杂度O(m × n)队列的最大长度。C 代码classSolution{public:intorangesRotting(vectorvectorintgrid){intmgrid.size();intngrid[0].size();queuepairint,intq;// 存储腐烂橘子的坐标intfresh0;// 新鲜橘子数量intminutes0;// 经过的分钟数// 统计新鲜橘子并将腐烂橘子入队for(inti0;im;i){for(intj0;jn;j){if(grid[i][j]1)fresh;elseif(grid[i][j]2)q.push({i,j});}}// 方向数组上、下、左、右intdirs[4][2]{{-1,0},{1,0},{0,-1},{0,1}};// 多源 BFSwhile(!q.empty()fresh0){intsizeq.size();// 每一层一分钟处理for(inti0;isize;i){auto[x,y]q.front();q.pop();for(autod:dirs){intnxxd[0],nyyd[1];if(nx0nxmny0nyngrid[nx][ny]1){grid[nx][ny]2;// 腐烂fresh--;q.push({nx,ny});}}}minutes;// 经过了一分钟}returnfresh0?minutes:-1;}};进阶思考如果网格规模很大如 10^5 × 10^5可以优化空间使用队列存储腐烂橘子坐标同时需要访问网格但网格无法全部加载需要分块处理或使用外部存储。本题中 m,n 很小BFS 即可高效求解。queue 详解std::queue是 C 标准库中的容器适配器提供 FIFO先进先出队列功能。它通常基于std::deque或std::list实现但默认使用std::deque。queue不提供迭代器只能访问队首和队尾元素。一、头文件与模板声明#includequeuetemplateclassT,classContainerstd::dequeTclassqueue;T元素类型。Container底层容器类型必须支持push_back()、pop_front()、front()、back()、size()、empty()等操作。默认为std::dequeT也可使用std::listT。二、构造函数与析构函数函数说明queue()默认构造空队列。queue(const Container cont)用容器cont的副本构造队列。queue(const queue other)拷贝构造。queue(queue other)移动构造。templateclass InputIt queue(InputIt first, InputIt last)(C23)用迭代器范围构造。~queue()析构函数。示例queueintq1;// 空队列queueintq2(q1);// 拷贝构造queueintq3(std::move(q2));// 移动构造三、元素访问函数说明front()返回队首元素的引用第一个元素。back()返回队尾元素的引用最后一个元素。注意调用前需确保队列非空否则行为未定义。示例q.push(1);q.push(2);coutq.front();// 1coutq.back();// 2四、容量函数说明empty()返回队列是否为空。size()返回队列中元素个数。示例if(!q.empty())coutq.size();五、修改器函数说明push(const T value)在队尾添加一个元素拷贝。push(T value)(C11)在队尾添加一个元素移动。emplace(Args... args)(C11)在队尾原地构造一个元素。pop()删除队首元素无返回值。swap(queue other)交换两个队列的内容。示例q.push(10);// 拷贝插入q.emplace(20);// 原地构造q.pop();// 删除队首q.swap(q2);// 交换六、底层容器相关类型别名类型说明container_type底层容器类型如std::dequeT。value_type元素类型。size_type无符号整数类型通常为size_t。reference元素引用类型。const_reference常量元素引用类型。示例queueint::container_type contq._Get_container();// 非标准但某些实现提供七、非成员函数函数说明operator比较两个队列是否相等元素逐个比较。operator!不等。operator字典序小于。operator字典序小于等于。operator字典序大于。operator字典序大于等于。swap(queue, queue)全局交换函数。示例if(q1q2){...}swap(q1,q2);八、完整示例#includeiostream#includequeueintmain(){std::queueintq;// 插入元素q.push(1);q.push(2);q.push(3);// 访问std::coutfront: q.front(), back: q.back()\n;// 1, 3// 遍历需要弹出无法迭代while(!q.empty()){std::coutq.front() ;q.pop();}std::cout\n;// 容量std::coutsize: q.size(), empty: q.empty()\n;// 使用 emplaceq.emplace(4);q.emplace(5);std::coutfront: q.front(), back: q.back()\n;// 4, 5// 交换std::queueintq2;q2.push(10);q2.push(20);q.swap(q2);std::coutafter swap, q front: q.front()\n;// 10return0;}九、总结std::queue是简洁的 FIFO 容器提供基本的入队、出队、访问队首队尾、判空和取大小操作。它不提供迭代器因此无法遍历内部元素而不破坏队列。如果需要遍历可考虑std::deque或std::list直接操作。在 BFS 等算法中queue是核心工具配合push和pop使用。