题解 | #疯牛病II#

考察的知识点：队列、广度优先搜索；

解答方法分析：

1. 遍历 pasture 矩阵，将初始病牛的位置加入队列，并统计初始健康牛的数量。
2. 使用 while 循环，当队列不为空时执行以下步骤：取队列头部的位置，将其从队列中弹出。遍历四个方向的相邻位置，若该位置是健康牛，则将其感染为病牛，并将其加入队列末尾，并更新感染时间的最大值。每次感染一个健康牛时，将健康牛的数量减1。
3. 如果所有健康牛都被感染，则返回蔓延的时间；否则，返回 -1。

所用编程语言：C++；

完整编程代码：↓

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pasture int整型vector<vector<>>
     * @return int整型
     */
    int healthyCowsII(vector<vector<int> >& pasture) {
        using Triple = array<int, 3>;
        const int directions[5] = {-1, 0, 1, 0, -1};

        int m = pasture.size(), n = pasture[0].size();
        queue<Triple> q;
        int cnt = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (pasture[i][j] == 2) q.push({i, j, 0});
                else if (pasture[i][j] == 1) ++cnt;
            }
        }
        int ans = 0;
        while (!q.empty()) {
            auto [i, j, p] = q.front();
            q.pop();
            for (int k = 0; k < 4; ++k) {
                int x = i + directions[k], y = j + directions[k + 1];
                if (x >= 0 && x < m && y >= 0 && y < n && pasture[x][y] == 1) {
                    --cnt;
                    pasture[x][y] = 2;
                    q.push({x, y, p + 1});
                    ans = max(ans, p + 1);
                }
            }
        }
        return cnt > 0 ? -1 : ans;
    }
};