题解 | #疯牛病II#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pasture int整型二维数组
     * @return int整型
     */
    public static boolean spot = false;
    public static int amount = 0;
     public int healthyCowsII (int[][] pasture) {
        if(totalHealth(pasture)==0){
            return 0;
        }
        int count = 0;
        int[][] flag = new int[pasture.length][pasture[0].length];
        for (int i = 0; i < flag.length; i++) {
            for (int j = 0; j < flag[0].length; j++) {
                flag[i][j] = pasture[i][j];
                if (pasture[i][j] == 1) {
                    count++;
                }
            }
        }
        search(pasture, flag, 0, count);
        if (spot) {
            return -1;
        }
        return amount;
    }
    public static void search(int[][] pasture, int[][] flag, int count,int cur) {
        for (int i = 0; i < pasture.length; i++) {
            System.arraycopy(flag[i], 0, pasture[i], 0, pasture[i].length);
        }
        for (int i = 0; i < pasture.length; i++) {
            for (int j = 0; j < pasture[i].length; j++) {
                if (pasture[i][j] == 2) {
                    if (i >= 1) {
                        flag[i - 1][j] = flag[i - 1][j] == 0 ? 0 : 2;;
                    }
                    if (i < pasture.length - 1) {
                        flag[i + 1][j] = flag[i + 1][j] == 0 ? 0 : 2;;
                    }
                    if (j >= 1) {
                        flag[i][j - 1] = flag[i][j - 1] == 0 ? 0 : 2;;
                    }
                    if (j < pasture[0].length - 1) {
                        flag[i][j + 1] = flag[i][j + 1] == 0 ? 0 : 2;
                    }
                }
            }
            System.out.println(Arrays.toString(flag[i]));
        }
        System.out.println();
        if (totalHealth(flag) == 0) {
            amount = count + 1;
            return;
        } else if (totalHealth(flag) == cur) {
            spot = true;
            return;
        }
        search(pasture, flag, count + 1, totalHealth(flag));
    }

    public static int totalHealth(int[][] flag) {
        int count = 0;
        for (int i = 0; i < flag.length; i++) {
            for (int j = 0; j < flag[0].length; j++) {
                if (flag[i][j] == 1) {
                    count++;
                }
            }
        }
        return count;
    }

}

本题考察的知识点是递归，所用编程语言是java.

本题相比上题不知道是否会全部变成疯牛，关于是否会全部变成疯牛可以考虑经过一分钟之后健康的牛数目是否会发生变化，如果健康的牛数目已经为0，则停止继续遍历下去，返回所用的时间；如果健康的牛数目不为0，且不会发生变化说明不管再过多少时间都不会全部变成疯牛，应该返回-1，否则应该继续递归下去，观察下一分钟疯牛的数目变化。