题解 | #疯牛病II#

function healthyCowsII(pasture) {
    let pastureStr = null // 记录当前牧场的状态字符串
    let min = 0 // 最小操作次数

    function check(arr) {
        if (arr.join('') === pastureStr) { // 如果当前牧场状态与上一次相同，则退出递归
            return
        }

        min++ // 操作次数加1

        let row = arr.length - 1 // 牧场行数
        let col = arr[0].length - 1 // 牧场列数

        let indexArr = [] // 存储需要操作的牛的坐标

        for (let i = 0; i <= row; i++) {
            for (let j = 0; j <= col; j++) {
                if (arr[i][j] === 2) { // 找到需要操作的牛
                    // 上
                    if (i - 1 >= 0 && arr[i - 1][j] === 1) {
                        indexArr.push({ i: i - 1, j: j }) // 将需要操作的牛的坐标保存起来
                    }

                    // 下
                    if (i + 1 <= row && arr[i + 1][j] === 1) {
                        indexArr.push({ i: i + 1, j: j })
                    }

                    // 左
                    if (j + 1 <= col && arr[i][j + 1] === 1) {
                        indexArr.push({ i: i, j: j + 1 })
                    }

                    // 右
                    if (j - 1 >= 0 && arr[i][j - 1] === 1) {
                        indexArr.push({ i: i, j: j - 1 })
                    }
                }
            }
        }

        pastureStr = arr.join('') // 更新当前牧场状态字符串

        indexArr.forEach((item) => { // 将需要操作的牛变为健康牛
            arr[item.i][item.j] = 2
        })

        check(arr) // 递归检查

    }

    check(pasture) // 调用check函数进行检查和操作

    for (let i = 0; i < pasture.length; i++) {
        for (let j = 0; j < pasture[0].length; j++) {
            if (pasture[i][j] === 1) {
                return -1 // 如果还有未被操作的牛，则返回-1
            }
        }
    }

    return min - 1 // 返回最小操作次数
}