题解 | #疯牛病II#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pasture int整型二维数组
     * @return int整型
     */
    public int healthyCowsII (int[][] pasture) {
        // write code here
        Queue<int[]> q = new LinkedList<>();
        int healthy_count = 0;
        for (int i = 0; i < pasture.length; i++) {
            for (int j = 0; j < pasture[0].length; j++) {
                if (pasture[i][j] == 2) {
                    q.offer(new int[] {i, j});
                }
                if (pasture[i][j] == 1) {
                    healthy_count++;
                }
            }
        }

        int[][] direction = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        int k = 0;
        while (!q.isEmpty() && healthy_count > 0) {
            k++;
            int node_size = q.size();
            while (node_size > 0) {
                int[] front_node = q.poll();
                for (int[] d : direction) {
                    int x = front_node[0] + d[0];
                    int y = front_node[1] + d[1];
                    if (x < 0 || y < 0 || x >= pasture.length || y >= pasture[0].length) {
                        continue;
                    }
                    if (pasture[x][y] == 2 || pasture[x][y] == 0) {
                        continue;
                    }
                    pasture[x][y] = 2;
                    healthy_count--;
                    q.offer(new int[] {x, y});
                }
                node_size--;
            }
        }

        if (healthy_count > 0) {
            return -1;
        }
        return k;
    }
}

代码使用的编程语言是Java。

该题考察的知识点：

• 二维数组的遍历和操作
• 队列的使用
• 广度优先搜索（BFS）

代码的文字解释大纲：

1. 在healthyCowsII方法中，创建一个队列q用于存储待处理的节点，以及一个整数变量healthy_count用于记录健康牛的数量
2. 使用嵌套的循环遍历二维数组pasture，并根据元素的值进行相应的处理：如果元素的值为2，表示当前位置有感染的牛，将其坐标加入队列q如果元素的值为1，表示当前位置有健康的牛，将healthy_count加1
3. 定义一个二维整型数组direction，其中包含四个方向的偏移量，用于确定邻居节点
4. 初始化一个整数变量k为0，用于记录传播的轮数
5. 使用循环进行广度优先搜索，直到队列为空或者所有健康的牛都被感染为止：在每一轮搜索中，首先记录队列中当前轮次的节点数量node_size依次处理当前轮次的节点：取出队列中的节点，并根据四个方向的偏移量计算邻居节点的坐标x和y如果邻居节点的坐标越界或者该位置的值为2（已感染）或0（没有牛），则忽略该节点否则，将邻居节点标记为感染，减少healthy_count的计数，并将该邻居节点加入队列q中以供下一轮搜索使用完成一轮搜索后，将轮数k加1
6. 若所有健康的牛都被感染，则返回轮数k；否则，返回-1。