题解 | #疯牛病II# BFS

知识点

多源BFS

思路

多源BFS，同时维护剩下的未感染的牛的个数和当前的所用的时间。如果跑完之后还有牛没感染，返回-1

时间复杂度

每个点只会入队一次，时间复杂度为

AC Code（C++）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pasture int整型vector<vector<>> 
     * @return int整型
     */
    using ai3 = array<int, 3>;
    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, -1, 0, 1};
    int healthyCowsII(vector<vector<int> >& pasture) {
        queue<ai3> q;
        int n = pasture.size(), m = pasture[0].size();
        int cnt = 0;
        for (int i = 0; i < n; i ++) {
            for (int j = 0; j < m; j ++) {
                if (pasture[i][j] == 2) q.push({i, j, 0});
                else if (pasture[i][j] == 1) cnt += 1;
            }
        }
        int res = 0;
        while (q.size() and cnt > 0) {
            auto [x, y, k] = q.front();
            q.pop();
            for (int i = 0; i < 4; i ++) {
                int nx = x + dx[i], ny = y + dy[i];
                if (nx >= 0 and ny >= 0 and nx < n and ny < m and pasture[nx][ny] == 1) {
                    pasture[nx][ny] = 2;
                    cnt -= 1;
                    res = max(res, k + 1);
                    q.push({nx, ny, k + 1});
                }
            }
        }
        return cnt > 0 ? -1 : res;
    }
};