题解 | #疯牛病II#

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pasture int整型vector<vector<>> 
     * @return int整型
     */

    // 广度优先搜索
    vector<pair<int,int>> v_p = {{-1,0},{1,0},{0,-1},{0,1}};

    int healthyCowsII(vector<vector<int> >& pasture) {
        // write code here
        int m = pasture.size();
        int n = pasture[0].size();
        // 遍历至d为空，
        deque<pair<int,int>> d;
        
        for(int i=0; i<m; ++i)
        {
            for(int j=0; j<n; ++j)
            {
                if(pasture[i][j]==2)
                    d.emplace_back(make_pair(i,j));
            }
        }

        int ans = -1;
        // 注意第0分钟完成了原本pasture中值为2的元素的遍历;
        while(!d.empty())
        {
            ++ans;
            for(auto [i_1,j_1]:d)
            {
                for(auto [i_2,j_2]:v_p)
                {
                    int i = i_1+i_2;
                    int j = j_1+j_2;

                    if(i>=0 && i<m && j>=0 && j<n && pasture[i][j]==1)
                    {
                        pasture[i][j] = 2;
                        d.emplace_back(make_pair(i,j));
                    }
                }
                d.pop_front();
            }
        }

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

        return ans;
    }
};