[数据结构与算法]LeetCode52-N皇后II-爆搜-递归

原题链接

Note：

几乎跟51N皇后一模一样了，直接整个变量按照上道题计数也行，或者改了一下代码，让dfs返回方案数

至于这个方案数返回什么0啊1啊什么的，找到最后一行的时候模拟一下就理解了

代码如下：

class Solution {
public:
    int n;
    vector<bool> col, dg, udg;

    int totalNQueens(int _n) {
        n = _n;
        col = vector<bool>(n);
        dg = udg = vector<bool>(n * 2);
        return dfs(0);
    }

    int dfs(int u){
        if(u == n)  //搜到最后了，是一个方案，返回1
            return 1;
        int res = 0;
        for(int i = 0; i < n; i ++){
            if(!col[i] && !dg[u - i + n] && !udg[u + i]){
                col[i] = dg[u - i + n] = udg[u + i] = true;
                //加上第u + 1行开始有多少种方案
                res += dfs(u + 1);
                col[i] = dg[u - i + n] = udg[u + i] = false;
            }
        }
        //返回从第u行开始往下搜，有多少种方案
        return res;
    }
};