LeetCode 52. N皇后 II

LeetCode 52. N皇后 II

思路：
参考下面的，与下面不同的就是返回的是res.size()

代码：

class Solution {
public:
    vector<vector<string>> ans;
    vector<bool> st,dg,udg;
    vector<string> path;

    int n;
    int totalNQueens(int _n) {
        //初始化
        n=_n;
        path=vector<string> (n,string(n,'.'));
        st=vector<bool> (n);
        dg=udg=vector<bool>(2*n);

        dfs(0);
        return ans.size();
    }

    void dfs(int u){
        if(u == n){
            ans.push_back(path);
        }
        //搜索顺序是每一行 枚举行中的每一列
        for(int i=0;i<n;i++){
            if(!st[i] && !dg[u-i+n] && !udg[i+u]){
                st[i]=dg[u-i+n]=udg[i+u]=true;
                path[u][i]='Q';
                dfs(u+1);
                st[i]=dg[u-i+n]=udg[i+u]=false;
                path[u][i]='.';
            }
        }
    }
};

class Solution {
public:
    int cnt = 0;
    vector<bool> st;
    vector<bool> dg, ndg;
    int n;

    int totalNQueens(int n) {
        this->n = n;
        st = vector<bool> (n);
        dg = ndg = vector<bool> (2 * n);

        dfs(0);
        return cnt;
    }

    void dfs(int u){
        //搜索的是行
        if(u == n){
            cnt ++;
            return;
        }

        for(int i = 0; i < n; i++){
            if(!st[i] && !dg[i + u] && !ndg[u + n - i]){
                st[i] = dg[i + u] = ndg[u + n - i] = true;
                dfs(u + 1);
                st[i] = dg[i + u] = ndg[u + n - i] = false;
            }
        }
    }
};