多源bfs

C++ 代码

#include <iostream>
#include <queue>
using namespace std;
using PII = pair<int, int>;
int n, m;
queue<PII> q;
vector<vector<char>> d;  // 原矩阵

int dxy[5] = {0, 1, 0, -1, 0};

int bfs(int cnt_1){
    int res = 0, cnt = 0;
    while(!q.empty()){
        int len = q.size();
        while(len --){
            PII t = q.front();
            q.pop();
            for(int i = 0; i < 4; ++ i){
                int x = t.first + dxy[i];
                int y = t.second + dxy[i + 1];
                if(x >= 0 && x < n && y >= 0 && y < m && d[x][y] == '1')
                {
                    d[x][y] = '2';
                    ++ cnt;
                    q.push({x, y});
                }
            }
        }
        ++ res;
    }
    if(cnt == cnt_1) return res - 1;
    return -1;
}

int main()
{
    string s;
    while(getline(cin, s)){
        vector<char> ans;
        for(int i = 0; i < s.size(); i += 2)
            ans.push_back(s[i]);
        d.emplace_back(ans);
    }
    n = d.size(), m = d[0].size();

    int cnt_1 = 0; // 产品经理的数量
    for(int i = 0; i < n; ++ i)
        for(int j = 0; j < m; ++ j)
        {
            if(d[i][j] == '2'){
                q.push({i, j});
            }else if(d[i][j] == '1')
                ++ cnt_1; 
        }

    cout << bfs(cnt_1) << endl;

    return 0;
}