题解 | #疯牛病I#

知识点

数组，广度优先遍历

解题思路

将全部为2的节点放到队列中。

当队列不为空并且k大于0时，我们将队列中的节点取出，将其上下左右为1的节点都置为2，再将其放入队列中。

其中我们可以用set来保存已经处理过的节点，减少判断

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 n = pasture.length, m = pasture[0].length;
        // 存放判断过的结点
        Set<Integer> set = new HashSet<>();
        Deque<int[]> deque = new LinkedList<>();
        int ans = m * n;
        // 把为2的添加进队列
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(pasture[i][j] == 2){
                    deque.offerFirst(new int[]{i,j});
                    set.add(i*m+j);
                    ans--;
                } else if(pasture[i][j] == 0) {
                    ans--;
                }
            }
        }
        // 四个方向
        int[][] point = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
        while(!deque.isEmpty() && k > 0){
            int size = deque.size();
            //遍历当前队列
            for(int i = 0; i < size; i++){
                int[] ints = deque.pollFirst();
                for(int j = 0; j < 4; j++){
                    int newY = ints[0] + point[j][0];
                    int newX = ints[1] + point[j][1];
                    if(set.contains(newY * m + newX) || newY < 0 || newY >= n || newX < 0 || newX >= m){
                        continue;
                    }
                    if(pasture[newY][newX] == 1){
                        deque.offerLast(new int[]{newY,newX});
                        set.add(newY * m + newX);
                        ans--;
                    }
                }
            }
            k--;
        }
        return ans;
    }
}