题解 | #疯牛病I#

考察知识点：广度优先搜索

题目分析：

可以通过队列进行广度优先搜索。每一次将病了的牛旁边健康的牛染病，并加入到队列中。每一分钟都是看当下队列中的所有牛，新加入的牛需要到下一分钟才访问，可以通过每次查询队列的size来控制。

在每一次将病了的牛旁边健康的牛染病时，可以通过数组 int dx[4] = {1, 0, -1, 0};和 int dy[4] = {0, 1, 0, -1};来遍历四个方向，看这四个方向中哪一个方向是健康的牛，再将其染病。

所用编程语言：C++

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pasture int整型vector<vector<>> 
     * @param k int整型 
     * @return int整型
     */
    int healthyCows(vector<vector<int> >& pasture, int k) {
        // write code here
        int m = pasture.size();
        int n = pasture[0].size();
        int res = 0;

        queue<pair<int , int>> illcows;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pasture[i][j] == 2) 
                    illcows.push({i, j});
                else if (pasture[i][j] == 1) 
                    res++;
            }
        }

        int dx[4] = {1, 0, -1, 0};
        int dy[4] = {0, 1, 0, -1};

        while (k > 0) {
            int size = illcows.size();
            while (size) {
                size--;
                pair<int, int> illcow = illcows.front();
                illcows.pop();
                int row = illcow.first;
                int col = illcow.second;
                for (int i = 0; i < 4; i++) {
                    int irow = row + dx[i];
                    int icol = col + dy[i];
                    if (irow >= 0 && irow < m && icol >= 0 && icol < n && pasture[irow][icol] == 1) {
                        pasture[irow][icol] = 2;
                        res--;
                        illcows.push({irow, icol});
                    }
                }
            }
            k--;
        }
        return res;
    }
};