xx51-n皇后

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻99击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1：

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1
输出：[["Q"]]

提示：

• 1 <= n <= 9

题解:

class Solution {
public:
    vector<vector<string>>ans;
    //用来判断新插入的Q是否合法
    bool legal(int n,int row,int lis,vector<string>& queen){
        //检查列,不查行因为是从一行一行往下进行插入的
        for (int i = 0; i < row; i++){
            if(queen[i][lis]=='Q') return false;
        }
        //45度 ,只用向上验证,下面的行都没有插入
        for (int i = row-1,j=lis-1; i>=0&&j>=0; i--,j--){
            if (queen[i][j]=='Q') return false;
        }
        //135度,同样只用向上验证
        for (int i = row-1,j=lis+1; i>=0&&j<n; i--,j++)
        {
            if (queen[i][j]=='Q') return false;
        }
        return true; 
    }
//row是行，一行一行得向下插入row的范围是从[0，n-1]
    void bt(int n,int row,vector<string>& queen){
        if(row==n) {
            ans.push_back(queen);
            return;
        }
        //遍历行，其中在回溯的过程中已经排除了行内非法的情况
        for (int i = 0; i <n ; i++)
        {
            if(legal(n,row,i,queen)){
                queen[row][i]='Q';
                bt(n,row+1,queen);
                queen[row][i]='.';
            }
        }
    }

    vector<vector<string>> solveNQueens(int n) {
        //先定义一个n*n的 . 组成的string容器
        vector<string>queen(n,string(n,'.'));
        bt(n,0,queen);
        return ans;

    }
};