题解 | #疯牛病I#

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

    // 方法二：广度优先搜索
    vector<vector<int>> dp = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    int healthyCows(vector<vector<int> >& pasture, int k) {
        deque<pair<int,int>> d;
        int m = pasture.size();
        int n = pasture[0].size();
        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));
            }
        }

        while(!d.empty() && k-->0)
        {
            for(auto [i,j]:d)
            {
                for(auto t_dp:dp)
                {
                    int t_i = i+t_dp[0];
                    int t_j = j+t_dp[1];
                    if(t_i>=0 && t_i<m && t_j>=0 && t_j<n && pasture[t_i][t_j]==1)
                    {
                        d.emplace_back(make_pair(t_i,t_j));
                        pasture[t_i][t_j] = 2;
                    }
                }
                d.pop_front();
            }
        }

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

        return ans;
    }

    // vector<vector<int>> dp = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    // int ans = 0;
    // void myHealthyCows(vector<vector<int>>& pasture, int k, int r, int c)
    // {
    //     if(k<=0)
    //         return;
    //     int m = pasture.size();
    //     int n = pasture[0].size();

    //     for(int i=0; i<4; ++i)
    //     {
    //         int t_r = dp[i][0]+r;
    //         int t_c = dp[i][1]+c;
    //         // cout << k << ", " << t_r << ", " << t_c << endl;

    //         if(t_r>=0 && t_r<m && t_c>=0 && t_c<n && pasture[t_r][t_c]==1)
    //         {
    //             pasture[t_r][t_c] = -1;
    //             // k-1就可以，--k就不行，估计是--k相当于引用
    //             myHealthyCows(pasture, k-1, t_r, t_c);
    //         }
    //     }
    // }

    // int healthyCows(vector<vector<int> >& pasture, int k) {
    //     // write code here
    //     int row = pasture.size();
    //     int col = pasture[0].size();

    //     for(int i = 0; i < row; ++i)
    //     {
    //         for(int j = 0; j < col; ++j)
    //         {
    //             if(pasture[i][j]==2)
    //                 myHealthyCows(pasture, k, i, j);
    //         }
    //     }

    //     for(int i = 0; i < row; ++i) 
    //     {
    //         for(int j = 0; j < col; ++j) 
    //         {
    //             cout << pasture[i][j] << "  ";
    //             if(pasture[i][j]==1)
    //                 ++ans;
    //         }
    //         cout << endl;
    //     }

    //     return ans;
    // }
};