题解 | #疯牛病I#

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 m = pasture.length;
        int n = pasture[0].length;
        Queue<int[]> infectedQueue = new LinkedList<>();
        int healthyCount = 0;

        // Initialize the infected queue and count healthy cows
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pasture[i][j] == 1) {
                    healthyCount++;
                } else if (pasture[i][j] == 2) {
                    infectedQueue.offer(new int[] {i, j});
                }
            }
        }

        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        // Simulate the spread of disease using BFS
        while (!infectedQueue.isEmpty() && k > 0) {
            int size = infectedQueue.size();
            for (int i = 0; i < size; i++) {
                int[] current = infectedQueue.poll();
                for (int[] direction : directions) {
                    int newRow = current[0] + direction[0];
                    int newCol = current[1] + direction[1];
                    if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n &&
                            pasture[newRow][newCol] == 1) {
                        pasture[newRow][newCol] = 2; // Infect the healthy cow
                        infectedQueue.offer(new int[] {newRow, newCol});
                        healthyCount--;
                    }
                }
            }
            k--;
        }

        return healthyCount;
    }
}

知识点分析：

1. 广度优先搜索（BFS）：通过队列实现BFS，逐层遍历，模拟疾病传播过程。
2. 二维数组的遍历：通过两重循环遍历二维数组中的每个单元格。
3. 邻居方向：利用一个方向数组表示四个方向的移动，从而找到相邻的单元格。
4. 队列：使用队列来保存感染牛的坐标，实现BFS过程。

解题思路：

在代码中，我们通过队列实现BFS，从已感染的牛开始向外蔓延，同时记录下被感染的健康牛的数量。经过k分钟的传播后，我们返回剩余的健康牛数。