class Solution {
public:
    vector<vector<string>>res;
    vector<string>cur;
    vector<int>col_vec;//已经放置的列
    vector<vector<string>> solveNQueens(int n) {
        bool**table=new bool*[n];
        for(int i=0;i<n;i++)table[i]=new bool[n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                table[i][j]=true;
            }
        }
        dfs(0,n,table);
        return res;
    }
    //逐行放置于第 0,1,2,.....,n-1行
    void dfs(int queen_num,int n,bool**table){
        //在第queen_num行放置棋子
        if(queen_num==n){
            res.push_back(cur);
            return;
        }
        for(int i=0;i<n;i++){
            //尝试放置于第i列
            if(table[queen_num][i]){
                string cur_string;
                for(int j=0;j<i;j++)cur_string+='.';
                cur_string+='Q';
                for(int j=0;j<n-i-1;j++)cur_string+='.';
                set_table(queen_num,i,table,n);
                cur.push_back(cur_string);
                col_vec.push_back(i);
                dfs(queen_num+1,n,table);
                col_vec.pop_back();
                reset_table(queen_num,i,table,n);
                for(int k=0;k<col_vec.size();k++){
                    set_table(k,col_vec[k],table,n);
                }
                cur.pop_back();
            }
        }
    }
    void reset_table(int queen_num,int col,bool**table,int n){
        for(int j=0;j<n;j++)table[queen_num][j]=true;//第queen_num行可以放置
        for(int j=0;j<n;j++)table[j][col]=true;//第col列可以放置
        //将对角线设置为可以放置
        int i=queen_num,j=col;
        while(i>=0&&j>=0){
            //左上
            table[i--][j--]=true;
        }
        i=queen_num,j=col;
        while(i<n&&j>=0){
            //左下
            table[i++][j--]=true;
        }
        i=queen_num,j=col;
        while(i>=0&&j<n){
            //右上
            table[i--][j++]=true;
        }
        i=queen_num,j=col;
        while(i<n&&j<n){
            //右下
            table[i++][j++]=true;
        }
    }
    void set_table(int queen_num,int col,bool**table,int n){
        for(int j=0;j<n;j++)table[queen_num][j]=false;//第queen_num行禁止放置
        for(int j=0;j<n;j++)table[j][col]=false;//第col列禁止放置
        //将对角线设置为禁止放置
        int i=queen_num,j=col;
        while(i>=0&&j>=0){
            //左上
            table[i--][j--]=false;
        }
        i=queen_num,j=col;
        while(i<n&&j>=0){
            //左下
            table[i++][j--]=false;
        }
        i=queen_num,j=col;
        while(i>=0&&j<n){
            //右上
            table[i--][j++]=false;
        }
        i=queen_num,j=col;
        while(i<n&&j<n){
            //右下
            table[i++][j++]=false;
        }
    }
};