题解 | #牛吃草问题#

知识点：

DFS/剪枝/位运算

分析：

使用常规深度优先一层层搜索

使用三个整形分别标记每一层哪些草场可以放置牛牛，这三个整形分别代表列、左斜下、右斜下（_col, ld, rd_），二进制位为 111 代表不能放置，000 代表可以放置

两个位运算：

x & -x 代表除最后一位 111 保留，其它位全部为 000

x & (x - 1) 代表将最后一位 111 变成 000

编程语言：

C++

完整代码：

    int res = 0;
    void dfs(int n, int row, int col, int ld, int rd) {
        if (row >= n) {
            res++;
            return;
        }
        int bits = ~(col | ld | rd) & ((1 << n) - 1);
        while (bits > 0) {
            int pick = bits & -bits; 
            dfs(n, row + 1, col | pick, (ld | pick) << 1, (rd | pick) >> 1);
            bits &= bits - 1;
        }
    }

    int totalNCow(int n) {
        dfs(n, 0, 0, 0, 0);
        return res;
    }