题解 | #疯牛病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] = 4; // Infect the healthy cow
                        infectedQueue.offer(new int[] {newRow, newCol});
                        healthyCount--;
                    }
                }
            }
            k--;
        }

        return healthyCount;
    }
}