题解 | #牛吃草问题# java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return int整型
     */
    public int totalNCow (int n) {
        // write code here
        int[] cols = new int[n];
        Arrays.fill(cols, -1);
        int[] count = new int[1];
        backtrack(cols, 0, count);
        return count[0];
    }

    private void backtrack(int[] cols, int row, int[] count) {
        int n = cols.length;
        if (row == n) {
            count[0]++;
            return;
        }

        for (int col = 0; col < n; col++) {
            if (isValid(cols, row, col)) {
                cols[row] = col;
                backtrack(cols, row + 1, count);
                cols[row] = -1;
            }
        }
    }

    private boolean isValid(int[] cols, int row, int col) {
        for (int i = 0; i < row; i++) {
            if (cols[i] == col || Math.abs(cols[i] - col) == Math.abs(i - row)) {
                return false;
            }
        }
        return true;
    }
}

编程语言是Java。

该题考察的知识点是回溯算法和递归。

代码的文字解释大纲如下：

1. 在 totalNCow 方法中，接收一个整数 n 作为参数，表示牛的数量。创建一个长度为 n 的整型数组 cols，并将数组所有元素初始化为 -1。创建一个长度为 1 的整型数组 count，用于存储放置方案的数量。
2. 调用 backtrack 方法进行回溯搜索，传入 cols、0（表示从第一行开始放置）、count 作为参数。
3. 在 backtrack 方法中，接收一个整型数组 cols、一个整数 row 和一个整型数组 count 作为参数。
4. 获取 cols 数组的长度，并判断 row 是否等于 n。如果等于，说明放置的牛的数量已经达到了 n，表示找到了一个有效的放置方案，将 count[0] 加一并返回。
5. 使用循环从 0 遍历到 n-1，遍历每一个列位置 col。判断当前位置是否满足条件，即不与其他已放置的牛冲突。调用 isValid 方法进行判断。如果满足条件，则将牛放置在当前位置 col。递归调用 backtrack 方法，将 row+1 作为下一行放置牛的起始位置，并传入 cols 和 count。递归调用结束后，进行回溯操作，将当前位置的牛移除，即将 cols[row] 的值设为 -1。
6. 在 isValid 方法中，接收一个整型数组 cols、一个整数 row 和一个整数 col 作为参数。遍历已放置的牛所在的行 i，判断当前位置 col 是否与已放置的牛的位置 cols[i] 相等，或者它们之间的列距离与行距离相等。如果存在冲突，返回 false；否则，返回 true。