题解 | #疯牛病II#

class Solution {
  public:
    int healthyCowsII(vector<vector<int> >& pasture) {
        int dx[4] = {-1, 1, 0, 0};
        int dy[4] = {0, 0, 1, -1};
        int m = pasture.size(), n = pasture[0].size();
        queue<pair<int, int>> queue;
        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pasture[i][j] == 2) queue.push({i, j});
                else if (pasture[i][j] == 1) count++;
            }
        }
        if (count == 0) return 0; //特判
        int flag;
        int min = 0;
        while (!queue.empty()) {
            int size = queue.size();
            flag = 0;
            for (int i = 0; i < size; i++) {
                auto [x, y] = queue.front();
                queue.pop();
                for (int j = 0; j < 4; j++) {
                    int ix = x + dx[j], iy = y + dy[j];
                    if (ix < 0 || ix >= m || iy < 0 || iy >= n || pasture[ix][iy] != 1) continue;
                    pasture[ix][iy] = 2;
                    queue.push({ix, iy});
                    count--;
                    flag = 1;  //标记这一分钟出现了感染，若该循环未出现感染则程序结束
                }
            }
            min++;
            if (count == 0) return min;
            if (!flag) return -1;
        }
        return count;
    }
};