leetcode51. N 皇后

class Solution {
    char g[10][10];
    bool col[20],dg[20],udg[20];
    vector<vector<string>> res;//保存答案
    vector<string> str;//用于保存答案的每一行
public:
    void dfs(int u,int n){
        if(u==n){
            for(int i=0;i<n;i++){
                str.push_back(g[i]);
            }
            res.push_back(str);
            str.clear();//清空，防止污染
            return ;
        }
        for(int i=0;i<n;i++){
	    //每列、对角线和反对角线只能选择一个
            if(!col[i]&&!dg[u+i]&&!udg[i-u+n]){
                g[u][i]='Q';
                col[i]=dg[u+i]=udg[i-u+n]=true;
                dfs(u+1,n);
                g[u][i]='.';
                col[i]=dg[u+i]=udg[i-u+n]=false;
            }
        }
    }
    vector<vector<string>> solveNQueens(int n) {
            for(int i=0;i<n;i++)
                for(int j=0;j<n;j++)
                    g[i][j]='.';
            dfs(0,n);
            return res;
    }
};