题解 | #疯牛病I# BFS

知识点

BFS

思路

由每个病牛开始多源BFS即可，限定扩展的步数，最后统计未感染的牛即可。

时间复杂度

每个点最多入队一次，时间复杂度为

AC Code（C++）

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

        while (q.size()) {
            auto [x, y, t] = 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;
                    if (t - 1 > 0) q.push({nx, ny, t - 1});
                }
            }
        }

        int res = 0;
        for (int i = 0; i < n; i ++) {
            for (int j = 0; j < m; j ++) {
                if (pasture[i][j] == 1) res += 1;
            }
        }
        return res;
    }
};