题解 | #牛吃草问题# 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) { // 放置的牛的数量等于 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。

该题考察的知识点是回溯法

回溯法函数backtrack用于搜索所有可能的放置方案。在每一行中，通过遍历列的索引来尝试将牛放置在不冲突的位置上。如果当前位置满足条件，就将牛放置在该位置，然后继续递归地放置下一头牛。当放置的牛的数量等于n时，说明找到一个有效的放置方案，将结果计数器count加1并返回。如果尝试的位置不满足条件，就进行回溯，将当前位置的牛移除，尝试下一个位置。

函数isValid用于检查当前位置是否满足条件，即在同一列或同一对角线上没有其他已放置的牛。