Java 题解 | #疯牛病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[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};
        int m = pasture.length;
        int n = pasture[0].length;
        Queue<int[]> q = new LinkedList<>();
        int healthy = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pasture[i][j] == 2)
                    q.offer(new int[] {i, j});
                else if (pasture[i][j] == 1)
                    healthy++;
            }
        }
        if (healthy == 0)
            return 0;
        int time = 0;
        while (!q.isEmpty() && time < k) {
            time++;
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                int[] point = q.poll();
                int x = point[0];
                int y = point[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;
                    q.offer(new int[] {nx, ny});
                    healthy--;
                }
            }
        }
        return healthy;
    }
}

编程语言是Java。

该题考察的知识点包括：

• 多维数组的遍历
• 队列（Queue）的使用
• 广度优先搜索（BFS）算法

代码的文字解释如下：

1. 获取二维数组pasture的行数m和列数n，并创建一个队列q和变量healthy，用于记录健康牛的数量。
2. 使用双重循环遍历二维数组pasture，如果当前格子的值为2，则将其坐标加入队列q；如果当前格子的值为1，则健康牛的数量加一。
3. 如果健康牛的数量为0，直接返回0。
4. 初始化时间变量time为0，开始进行广度优先搜索。
5. 在每一轮搜索中，首先获取当前队列q中的元素个数sz，这个个数表示当前轮次需要处理的节点数量。
6. 依次处理队列中的每个节点，分别计算节点的横纵坐标x和y。
7. 对当前节点的四个相邻节点进行判断，如果相邻节点越界或者不为1，则忽略该节点。
8. 如果相邻节点为1，将其设置为2（表示感染），并将相邻节点的坐标加入队列q，然后健康牛的数量减一。
9. 搜索完成后，返回健康牛的数量作为结果。