c++ - 图形中的DFS需要多少时间间隔？

Question

问题:
假设您正在图形上进行广度优先搜索。您从特定点开始，然后向外扩展。在一个时间间隔内，在给定条件下，您“感染”了邻居。我想知道遍历整个图所需的时间间隔(即感染所有节点)。
这个问题是一个普遍的问题。但是，我将依靠LeetCode示例来提供可重现的内容。
我的方法:
Basic bfs using a queue。在每次迭代期间，我都将一个spacer元素插入队列。如果我找到了这个垫片，我知道一个时间间隔就到了。
队列q中的元素:

q: a, b, c, timer // a, b and c are infected at first moment in time
q: d, e, timer    // above elements infect, d and e.
q: timer          // we only have a timer, total traversal took 2 time intervals

为什么我的方法无效:
我的方法的基本缺陷是，如果元素会从多个方面被感染，则可能会将元素多次推送到 q。
带有队列 q的示例网格。 q存储图中节点的索引。 1健康， 2被感染:

1,1
2,2

q: {0,0}, {0,1}, timer // top 2 elements are in queue. They got infected by bottom 2 elements. 

处理第一个元素

2,1
2,2

q: {0,1}, timer, {0,1} 

处理第二个元素

2,2
2,2

q: timer, {0,1}, timer

我们将相同的元素两次推送到 q，导致时间不正确。 (时间== 2，而不是时间== 1)。
如何解决此错误？
来自LeetCode的示例问题:
我的方法曾经(不是)解决 LeetCode problem 994。

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;
        q.emplace(false);
        
        while(!q.empty()) {
            const position pos = q.front();
            q.pop();
            if (!pos.valid_ && !q.empty()) {
                ++minutes;
                q.emplace(false);
            }
            if (!pos.valid_) continue;
            
            // bfs next: top, right, bottom, left
            const size_t old_size = q.size();
            if (pos.i_ > 0) 
                if (grid.at(pos.i_ - 1).at(pos.j_) == 1) q.emplace(pos.i_ - 1, pos.j_);
            if (pos.j_ < grid.at(0).size() - 1)
                if (grid.at(pos.i_).at(pos.j_ + 1) == 1) q.emplace(pos.i_, pos.j_ + 1);
            if (pos.i_ < grid.size() - 1)
                if (grid.at(pos.i_  + 1).at(pos.j_) == 1) q.emplace(pos.i_  + 1, pos.j_);
            if (pos.j_ > 0)
                if (grid.at(pos.i_).at(pos.j_ - 1) == 1) q.emplace(pos.i_, pos.j_ - 1);
        
            if (grid.at(pos.i_).at(pos.j_) == 1) {
                --fresh_orange;
                grid.at(pos.i_).at(pos.j_) = 2;
            }
        }

        return fresh_orange == 0 ? minutes : -1;
    }
};

重现我的问题的输入: [[2,2],[1,1],[0,0],[2,0]]。

Answer 1

好的。我有一个(显而易见的)解决方案:您只需跟踪下一轮将感染谁。我正在使用-1作为“将很快被感染”的标记。
带有队列q的示例网格。 q存储图中节点的索引。 1健康，2被感染:

-1,-1
 2, 2

q: {0,0}, {0,1}, timer // top 2 elements are in queue. They got infected by bottom 2 elements. 

处理第一个元素

 2,-1
 2, 2

q: {0,1}, timer, // we do not push back {0,1} since we know it will have symptoms soon

处理第二个元素

2,2
2,2

q: time

对于那些对LeetCode解决方案感兴趣的人:

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;
        q.emplace(false);
        
        while(!q.empty()) {
            const position pos = q.front();
            q.pop();
            if (!pos.valid_ && !q.empty()) {
                ++minutes;
                q.emplace(false);
            }
            if (!pos.valid_) continue;
            
            // bfs next: top, right, bottom, left
            const size_t old_size = q.size();
            if (pos.i_ > 0) {                
                if (grid.at(pos.i_ - 1).at(pos.j_) == 1) {
                    grid.at(pos.i_ - 1).at(pos.j_) = -1;
                    q.emplace(pos.i_ - 1, pos.j_);
                }
            }
            if (pos.j_ < grid.at(0).size() - 1) {
                if (grid.at(pos.i_).at(pos.j_ + 1) == 1) {
                    grid.at(pos.i_).at(pos.j_ + 1) = -1;
                    q.emplace(pos.i_, pos.j_ + 1);
                }
            }
            if (pos.i_ < grid.size() - 1) {
                if (grid.at(pos.i_  + 1).at(pos.j_) == 1) {
                    grid.at(pos.i_  + 1).at(pos.j_) = -1;
                    q.emplace(pos.i_  + 1, pos.j_);
                }
            }
            if (pos.j_ > 0) {
                if (grid.at(pos.i_).at(pos.j_ - 1) == 1) {
                    grid.at(pos.i_).at(pos.j_ - 1) = -1;
                    q.emplace(pos.i_, pos.j_ - 1);
                }
            }
                
            if (grid.at(pos.i_).at(pos.j_) == 1 || grid.at(pos.i_).at(pos.j_) == -1) {
                --fresh_orange;
                grid.at(pos.i_).at(pos.j_) = 2;
            }
        }

        return fresh_orange == 0 ? minutes : -1;
    }
};