题解 | #疯牛病I#

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

题目考察的知识点

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

题目解答方法的文字分析

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

1. 首先，我们将所有患有疯牛病的牛的坐标加入队列，并记录当前的分钟数为 0。
2. 然后，在 BFS 过程中，我们每次从队列中取出一个患有疯牛病的牛的坐标，并将其周围 4 个方向上的健康牛的坐标加入队列，并将这些健康牛的状态设置为患有疯牛病（值为 2）。
3. 每当我们从队列中取出一个患有疯牛病的牛的坐标时，表示经过了一分钟，我们将当前分钟数加 1。
4. 循环直到队列为空或者分钟数达到 k。
5. 最后，我们统计 pasture 中健康牛（值为 1）的数量，并返回结果。

本题解析所用的编程语言

C++

完整且正确的编程代码

#include <vector>
#include <queue>

using namespace std;

class Solution {
public:
    /**
     * 模拟疯牛病的传播过程，并返回经过 k 分钟后剩下的健康牛的数量。
     * 
     * @param pasture int整型vector<vector<>>，表示牧场的状态
     * @param k int整型，经过的分钟数
     * @return int整型，剩下的健康牛的数量
     */
    int healthyCows(vector<vector<int>>& pasture, int k) {
        const int m = pasture.size();
        const int n = pasture[0].size();
        queue<pair<int, int>> infected_cows; // 存放患有疯牛病的牛的坐标
        int minutes = 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));
                }
            }
        }

        // 使用BFS模拟疯牛病的传播过程
        while (!infected_cows.empty() && minutes < k) {
            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));
                    }
                }
            }
            minutes++; // 经过的分钟数增加
        }

        // 统计剩下的健康牛的数量
        int healthy_count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pasture[i][j] == 1) {
                    healthy_count++;
                }
            }
        }

        return healthy_count;
    }
};

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