Java 题解 | #牛吃草问题#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return int整型
     */
    private int ans = 0;

    public int totalNCow(int n) {
        int[] pos = new int[n];
        help(pos, n, 0);
        return ans;
    }

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

    private void help(int[] pos, int n, int row) {
        if (row == n) {
            ans++;
            return;
        }
        for (int i = 0; i < n; i++) {
            if (isValid(pos, row, i)) {
                pos[row] = i;
                help(pos, n, row + 1);
            }
        }
    }
}

编程语言是Java。

该题考察的知识点是回溯算法（Backtracking）。

代码的文字解释如下：

1. 实现一个递归函数totalNCow，接受一个整数n作为参数，表示需要放置的皇后数量。
2. 在递归函数totalNCow中，定义一个整数数组pos，用于存储每个皇后所在的列位置。初始时，所有元素都设为0。
3. 实现一个辅助函数isValid，判断当前位置是否合法。遍历之前已放置的皇后，检查是否在同一列或对角线上。
4. 实现一个辅助函数help，用于递归放置皇后。如果已经放置了n个皇后，则将结果计数器ans加1并返回。
5. 在help函数中，遍历当前行的每个列，依次尝试放置皇后。如果当前位置合法，则将其记录在pos数组中，并递归调用help函数继续处理下一行。
6. 在主函数totalNCow中，调用help函数开始放置皇后。
7. 返回结果ans作为答案。