51. N皇后

class Solution {
public:
    vector<vector<string>> res;
    vector<string> chess;
    int N;
    bool checkpos(int i, int j) {
        for(int k=i+1;k<N;k++){
            if(chess[k][j]=='Q')return false;
        }
        for(int k=0;k<N;k++){
            int x = i+k;
            int y = j+k;
            if(x>=N||y>=N)break;
            if(chess[x][y]=='Q')return false;
        }
        for(int k=0;k<N;k++){
            int x = i+k;
            int y = j-k;
            if(x>=N||y<0)break;
            if(chess[x][y]=='Q')return false;
        }
        return true;
    }
    void bt(int depth) {
        if (depth < 0) {
            res.push_back(chess);
            return;
        }
        for(int pos=0;pos<N;pos++){
            if(checkpos(depth,pos)) {
                chess[depth][pos] = 'Q';
                bt(depth - 1);
                chess[depth][pos] = '.';
            }
        }
    }
    vector<vector<string>> solveNQueens(int n) {
        N=n;
        for (int i=0;i<n;i++){
            chess.push_back(string(n,'.'));
        }
        bt(n-1);
        return res;
    }
};

我是从棋盘底部从下往上构造的哈哈