题解 | #牛吃草问题#

知识点：dfs

思路：经典的八皇后问题，我们使用布尔数组来记录每一列、每一条正对角线和每一条反对角线上的皇后是否已被占用。在回溯过程中，我们在合适的位置放置皇后，并递归地继续放置下一个皇后。当放置完所有皇后时，我们计数器加一，表示找到了一种方案。然后我们需要撤销之前的选择，回溯到上一层，继续尝试其他的选择

编程语言：java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return int整型
     */
    public int totalNCow(int n) {
        boolean[] cols = new boolean[10];
        boolean[] d1 = new boolean[20];
        boolean[] d2 = new boolean[20];
        int[] res = new int[1];

        dfs(n, 0, cols, d1, d2, res);

        return res[0];
    }

    private void dfs(int n, int u, boolean[] cols, boolean[] d1, boolean[] d2,
                     int[] res) {
        if (u == n) {
            res[0]++;
            return;
        }

        for (int i = 0; i < n; i++) {
            if (cols[i] || d1[u + i] || d2[u - i + n])
                continue;

            cols[i] = true;
            d1[u + i] = true;
            d2[u - i + n] = true;

            dfs(n, u + 1, cols, d1, d2, res);

            cols[i] = false;
            d1[u + i] = false;
            d2[u - i + n] = false;
        }
    }
}