LeetCode 51. N 皇后

class Solution {
public:
    vector<vector<string>> res;
    vector<string> path;
    vector<bool> anti_diag,col,diag;
    void dfs(int n,int u)
    {
        if(u==n)
        {
            res.push_back(path);
            return;
        }
        string str(n,'.');
        for(int i=0;i<n;i++)//枚举皇后在该行的位置
        {
            if(!col[i]&&!diag[u+i]&&!anti_diag[u-i+n])
            {
                str[i]='Q';
                col[i]=diag[u+i]=anti_diag[u-i+n]=true;
                path.push_back(str);
                dfs(n,u+1);
                str[i]='.';
                col[i]=diag[u+i]=anti_diag[u-i+n]=false;
                path.pop_back();
            }
        }
    }
    vector<vector<string>> solveNQueens(int n) {
        col=vector<bool>(n,false);
        diag=anti_diag=vector<bool>(2*n,false);
        dfs(n,0);
        return res;
    }
};