[数据结构与算法]leetcode 51 N皇后

第一个自己独立做出来的hard，记录一下（但是风格不是很好，有待完善

因为每行有且只能有一个，所以可以按行遍历，判断每行的哪个位置上可以放。
col: 记录每行的某一列上是否已经放置皇后
dg:记录过该点正方形自左上至右下的对角线上是否放了皇后，下标表示是第几条对角线
udg:记录过该点正方形自右上至左下的对角线上是否放了皇后，下标表示是第几条对角线
yxc NB！！！！

AC代码：
时间优于91%，空间优于99%

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> ans;
        vector<bool> col(n,false), dg(2*n,false), udg(2*n,false);
        string init = "";
        for(int i = 0; i < n; i++){
            init += ".";
        }
        vector<string> perRow(n, init);
        dfs(0,ans,col,dg,udg,perRow);
        return ans;
    }

    void dfs(int u,vector<vector<string>> & ans,vector<bool> &col, vector<bool> &dg, vector<bool> &udg,vector<string> &perRow){
        int n = col.size();
        if(u == n ){
            ans.push_back(perRow);
            return;
        }

        for(int i = 0; i < n; i++){
            if(!col[i] && !dg[u+i] && !udg[n - u + i]){
                perRow[u][i] = 'Q';
                col[i] = dg[u+i] = udg[n - u + i] = true;
                dfs(u+1,ans,col,dg, udg,perRow);
                //恢复现场
                perRow[u][i] = '.';
                col[i] = dg[u+i] = udg[n - u + i] = false;
            }
        }

    }
};