题解 | #牛吃草问题# 八皇后问题 DFS

知识点

DFS 回溯

知识点

经典八皇后问题，从上到下一行一行填入，枚举填在哪一列，同时开三个布尔数组分别代表某列、某对角线、某副对角线是否被使用。回溯后记得恢复现场。时间复杂度为

AC code (C++)

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    int totalNCow(int n) {
        vector<bool> cols(10), d1(20), d2(20);
        int res = 0;
        function<void(int)> dfs = [&](int u) {
            if (u == n) {
                res += 1;
                return;
            }
            for (int i = 0; i < n; i ++) {
                if (cols[i] or d1[u + i] or d2[u - i + n]) continue;
                cols[i] = d1[u + i] = d2[u - i + n] = true;
                dfs(u + 1);
                cols[i] = d1[u + i] = d2[u - i + n] = false; 
            }
        };
        dfs(0);
        return res;
    }
};