题解 | #疯牛病I# java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pasture int整型二维数组
     * @param k int整型
     * @return int整型
     */
    public int healthyCows (int[][] pasture, int k) {
        // write code here
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};
        int m = pasture.length;
        int n = pasture[0].length;
        Queue<int[]> queue = new ArrayDeque<>();
        int healthy = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pasture[i][j] == 2)
                    queue.offer(new int[] {i, j});
                else if (pasture[i][j] == 1)
                    healthy++;
            }
        }

        if (healthy == 0) return 0;

        int time = 0;
        while (!queue.isEmpty() && time < k) {
            time++;
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                int[] curr = queue.poll();
                int x = curr[0];
                int y = curr[1];

                for (int j = 0; j < 4; j++) {
                    int nx = x + dx[j];
                    int ny = y + dy[j];

                    if (nx < 0 || nx >= m || ny < 0 || ny >= n || pasture[nx][ny] != 1)
                        continue;

                    pasture[nx][ny] = 2;
                    queue.offer(new int[] {nx, ny});
                    healthy--;
                }
            }
        }

        return healthy;
    }
}

编程语言是Java。

这道题考察了图的遍历和广度优先搜索（BFS）算法。

代码的文字解释：

• healthyCows 方法实现了在给定的二维牧场中，找到健康的奶牛数量。
• 将牧场中的初始状态进行初始化，并统计健康的奶牛数量。
• 使用队列 queue 存储当前已感染的奶牛的位置，并进行 BFS 遍历。
• 在 BFS 中，不断从队列中取出位置 (x, y)，并尝试感染其相邻的健康奶牛。如果相邻位置合法且为健康奶牛，则将其状态设为已感染，并将其加入队列，同时更新健康奶牛数量。
• 最终返回剩余的健康奶牛数量。