题解 | #疯牛病I#

#include <queue>
#include <utility>
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();
        queue<pair<int,int>> que;
        vector<pair<int,int>> moves={{-1,0},{1,0},{0,-1},{0,1}};
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(pasture[i][j] == 2){
                    que.push(make_pair(i,j));//放入疯牛病的坐标
                }
            }
        }
        int minute=0;
        while(!que.empty() && minute < k){
            int N = que.size();
            for(int i=0;i<N;i++){
                pair<int,int> point = que.front();
                que.pop();
                int x = point.first;
                int y = point.second;
                for(auto move:moves){
                    int nx = x + move.first;
                    int ny = y + move.second;
                    if(nx>=0 && nx<m && ny>=0 && ny<n && pasture[nx][ny]==1){
                        pasture[nx][ny]=2;
                        que.push(make_pair(nx,ny));
                    }
                }
            }
            minute++;
        }
        int count = 0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(pasture[i][j] == 1){
                    count++;
                }
            }
        }
        return count;
    }
};

dfs模拟上下左右扩散