BFS图遍历时间间隔计算错误的修复方案咨询（附LeetCode示例）

我完全懂你遇到的问题——在多源BFS的场景里（比如这道烂橘子问题），同一个健康节点可能被多个相邻的已感染节点同时“盯上”，导致多次被推入队列，最后时间计算结果比实际多。咱们来一步步修复这个bug。

核心问题分析 #

你当前代码的关键缺陷是：在弹出队列元素后才标记节点为已感染，但这时候其他相邻节点已经把这个健康节点推入队列了。比如你举的例子里，(0,1)节点被(1,1)和(0,0)同时感染，两次进入队列，最终导致timer被多触发一次，时间算成了2，但实际只需要1个时间间隔。

另外，你用timer分隔时间间隔的方式本身没问题，但因为重复入队的存在，会让timer的触发逻辑混乱，放大了错误。

修复方案 #

解决思路很直接：在将节点推入队列的瞬间，就立刻标记它为已感染状态，这样其他相邻节点再检查时，会发现它已经不是健康节点，就不会重复推入队列了。

同时，我们可以把时间计算逻辑改成按“层级”处理：每次处理当前队列里的所有节点（这一层的所有已感染节点），处理完这一层后时间加1，这样更直观，也能避免timer带来的额外问题。

修改后的代码及解释 #

下面是针对你原代码的修改版本，我标注了关键改动点：

class Solution {
 struct position {
 position(size_t i, size_t j) : i_(i), j_(j), valid_(true) {}
 position(bool valid) : i_(0), j_(0), valid_(valid) {}
 const size_t i_;
 const size_t j_;
 const bool valid_;
 };
public:
 int orangesRotting(vector<vector<int>>& grid) {
 if (grid.empty()) return -1;
 size_t fresh_orange = 0;
 std::queue<position> q;
 // 初始化：统计新鲜橘子，将所有初始烂橘子入队
 for (size_t i = 0; i < grid.size(); ++i) {
 for (size_t j = 0; j < grid.at(0).size(); ++j) {
 int orange = grid.at(i).at(j);
 if (orange == 1) {
 ++fresh_orange;
 } else if (orange == 2) {
 q.emplace(i, j);
 }
 }
 }
 
 size_t minutes = 0;
 // 按层级处理BFS：每次处理当前队列的所有节点（当前时间间隔的感染源）
 while (!q.empty() && fresh_orange > 0) {
 int current_level_size = q.size(); // 当前层的节点数
 // 处理当前层的所有节点
 for (int k = 0; k < current_level_size; ++k) {
 const position pos = q.front();
 q.pop();
 // 检查四个方向的相邻节点
 if (pos.i_ > 0 && grid.at(pos.i_ - 1).at(pos.j_) == 1) {
 grid.at(pos.i_ - 1).at(pos.j_) = 2; // 立刻标记为烂橘子，避免重复入队
 --fresh_orange;
 q.emplace(pos.i_ - 1, pos.j_);
 }
 if (pos.j_ < grid.at(0).size() - 1 && grid.at(pos.i_).at(pos.j_ + 1) == 1) {
 grid.at(pos.i_).at(pos.j_ + 1) = 2;
 --fresh_orange;
 q.emplace(pos.i_, pos.j_ + 1);
 }
 if (pos.i_ < grid.size() - 1 && grid.at(pos.i_ + 1).at(pos.j_) == 1) {
 grid.at(pos.i_ + 1).at(pos.j_) = 2;
 --fresh_orange;
 q.emplace(pos.i_ + 1, pos.j_);
 }
 if (pos.j_ > 0 && grid.at(pos.i_).at(pos.j_ - 1) == 1) {
 grid.at(pos.i_).at(pos.j_ - 1) = 2;
 --fresh_orange;
 q.emplace(pos.i_, pos.j_ - 1);
 }
 }
 // 处理完一层，时间加1
 ++minutes;
 }
 
 // 如果还有新鲜橘子没被感染，返回-1，否则返回时间
 return fresh_orange == 0 ? minutes : -1;
 }
};

关键改动说明： #

1. 提前标记已感染节点：在发现相邻节点是新鲜橘子时，立刻将其设为2（烂橘子），再推入队列。这样其他方向的节点再检查时，就不会把它重复加入队列。
2. 按层级计算时间：每次记录当前队列的大小（当前时间间隔的所有感染源），处理完这所有节点后，时间加1。这样完全避免了timer分隔带来的重复触发问题。
3. 终止条件优化：当队列空了或者没有新鲜橘子了，就停止循环，避免不必要的计算。

测试输入验证 #

用你提到的测试输入[[2,2],[1,1],[0,0],[2,0]]来验证：

• 初始队列里有(0,0)、(0,1)、(3,0)三个烂橘子，新鲜橘子数是2（(1,0)和(1,1)）。
• 第一次处理这三个节点：
  • (0,0)感染(1,0)，标记为2，新鲜橘子减1，入队。
  • (0,1)感染(1,1)，标记为2，新鲜橘子减1，入队。
  • (3,0)周围没有新鲜橘子，无操作。
• 处理完这一层，minutes加1（变为1）。
• 接下来队列里是(1,0)和(1,1)，但此时新鲜橘子已经为0，循环终止。
• 最终返回1，符合实际正确结果。

内容的提问来源于stack exchange，提问作者User12547645