N-Queens .2.cpp

class Solution {
public:
    vector<vector<string> > solveNQueens(int n) {
        vector<vector<string>>ret;
        vector<string>tmp(n,string(n,'.'));
        set<int>s1,s2,s3;
        dfs(ret,tmp,s1,s2,s3,n,0);
        return ret;
    }
    void dfs(vector<vector<string>>&ret,vector<string>&tmp,set<int>&s1,set<int>&s2,set<int>&s3,int n,int cur){
        if(n==cur)
            ret.push_back(tmp);
        else{
            for(int i=0;i<n;i++)
                if(s1.count(i)==0 && s2.count(i+cur)==0 && s3.count(i-cur)==0){
                    tmp[cur][i]='Q';
                    s1.insert(i);
                    s2.insert(i+cur);
                    s3.insert(i-cur);
                    dfs(ret,tmp,s1,s2,s3,n,cur+1);
                    s1.erase(i);
                    s2.erase(i+cur);
                    s3.erase(i-cur);
                    tmp[cur][i]='.';
                }
        }
    }
};