52. N 皇后 II

class Solution {
public:
    vector<bool> row,anti_diag,col,diag;
    int res=0;
    void dfs(int n,int x,int y,int cnt)
    {
        
        if(y==n)    y=0,x++;
        if(x==n)
        {   
            if(cnt==n)
                res++;
            return;
        }
        if(!row[x]&&!col[y]&&!diag[x+y]&&!anti_diag[x-y+n])
        {
            row[x]=col[y]=diag[x+y]=anti_diag[x-y+n]=true;
            dfs(n,x,y+1,cnt+1);
            row[x]=col[y]=diag[x+y]=anti_diag[x-y+n]=false;
        }
        dfs(n,x,y+1,cnt);
    }
    int totalNQueens(int n) {
        row=col=vector<bool>(n,false);
        diag=anti_diag=vector<bool>(2*n,false);
        dfs(n,0,0,0);
        return res;
    }
};