大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

本题考察广度优先搜索（BFS）算法，需要模拟疯牛病的传播过程，并计算经过的分钟数。

题目解答方法的文字分析

我们可以通过 BFS 来模拟疯牛病的传播过程：

  1. 首先，我们将所有患有疯牛病的牛的坐标加入队列，并记录当前的分钟数为 0。
  2. 然后，在 BFS 过程中，我们每次从队列中取出一个患有疯牛病的牛的坐标，并将其周围 4 个方向上的健康牛的坐标加入队列，并将这些健康牛的状态设置为患有疯牛病（值为 2）。
  3. 每当我们从队列中取出一个患有疯牛病的牛的坐标时，表示经过了一分钟，我们将当前分钟数加 1。
  4. 循环直到队列为空。
  5. 在 BFS 过程中，我们需要记录牧场中健康牛的数量，当经过的分钟数超过牧场中健康牛的数量时，我们可以停止 BFS 并返回 -1，表示不可能到达没有健康的牛的情况。
  6. 最后，返回经过的分钟数即可。

本题解析所用的编程语言

C++

完整且正确的编程代码

#include <vector>
#include <queue>

using namespace std;

class Solution {
public:
    /**
     * 模拟疯牛病的传播过程，并返回直到牧场中没有健康的牛为止所必须经过的最小分钟数。
     * 
     * @param pasture int整型vector<vector<>>，表示牧场的状态
     * @return int整型，直到没有健康的牛为止所必须经过的最小分钟数
     */
    int healthyCowsII(vector<vector<int>>& pasture) {
        const int m = pasture.size();
        const int n = pasture[0].size();
        queue<pair<int, int>> infected_cows; // 存放患有疯牛病的牛的坐标
        int minutes = 0; // 经过的分钟数
        int healthy_count = 0; // 健康牛的数量

        // 将患有疯牛病的牛的坐标加入队列
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pasture[i][j] == 2) {
                    infected_cows.push(make_pair(i, j));
                } else if (pasture[i][j] == 1) {
                    healthy_count++;
                }
            }
        }

        // 如果初始时没有健康的牛，则不需要进行 BFS
        if (healthy_count == 0) {
            return 0;
        }

        // 使用BFS模拟疯牛病的传播过程
        while (!infected_cows.empty()) {
            int size = infected_cows.size();
            while (size--) {
                int row = infected_cows.front().first;
                int col = infected_cows.front().second;
                infected_cows.pop();

                // 上下左右四个方向的偏移量
                int dx[] = {-1, 1, 0, 0};
                int dy[] = {0, 0, -1, 1};

                for (int d = 0; d < 4; d++) {
                    int nx = row + dx[d];
                    int ny = col + dy[d];

                    // 如果相邻的格子是健康的牛，则将其感染
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n && pasture[nx][ny] == 1) {
                        pasture[nx][ny] = 2;
                        infected_cows.push(make_pair(nx, ny));
                        healthy_count--; // 健康牛数量减少
                        if (healthy_count == 0) {
                            return minutes + 1; // 返回经过的分钟数
                        }
                    }
                }
            }
            minutes++; // 经过的分钟数增加
        }

        return -1; // 如果没有到达没有健康的牛的情况，返回 -1
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！