class Solution {
public:
    vector<vector<string>> result;
    vector<int>path;
    //求绝对值
    int abs(int a)
    {
        if (a < 0) return -a;
        else return a;
    }
    void backtraking(int n ,vector<bool> &used ,int deep)
    { 
      //当深度大于n时返回
        if(deep > n) return;
        //当路径为最大深度，找到路径存入
        if(path.size() == n)
        {
          //将数字路径转换成字符串路径
            vector<string> path_s;
            for(int i=0;i<n;i++)
            {
                string tmp ;
                for(int k=0;k<n;k++) tmp +='.';//建立n个.
                for(int j=0;j<n;j++)  if(j==path[i]) tmp[j] = 'Q';//在应该放Q的位置放Q
                path_s.push_back(tmp);//转换好的字符串存入路径
            }
            //存入结果
            result.push_back(path_s);
            return;
        }
    //层次循环，找到每一行的点。
        for(int i=0 ; i<n; i++)
        {
            if(used[i] == true) continue; //该点用过了，跳过。一个树枝的点只能用一次
            pair<int,int> x(deep,i);//当前可能有效点
            bool flag = true;
            //当前点，和path路径里面所有点依次对比
            for(int j =0 ; j < path.size() ;j++)
            {
                pair<int,int> y(j,path[j]);//path之前加入的点
                //检测当前点与之前路径点，是否在一列一行和对角线
                if( abs(x.first - y.first)==0 ||  abs(x.second - y.second)==0 
                    || abs(x.first - y.first) == abs(x.second - y.second) ) 
                    flag = false;
            }
            //检测是合格点，加入path
            if(flag == true)
            {
              //记录该点使用
                used[i] = true;
                path.push_back(i);
                //递归，深度+1（找下一行）
                backtraking(n,used,deep+1);
                path.pop_back();
                used[i] = false;
            }
        }
        return;
    }
    vector<vector<string>> solveNQueens(int n) { 
        vector<bool> used(n,false);
        backtraking(n ,used,0);
        return result;
    }
};