51. N-Queens

image.png
image.png

string的初始化：
参考：https://blog.csdn.net/allovexuwenqiang/article/details/4277555

image.png

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> result;
        if(n == 0) return result;
        vector<int> cols;
        search(n, cols, result);
        return result;
    }
private:
    bool isValid(vector<int>& cols, int col, int n){
        if(col < 0 || col >= n) return false;
        for(int i = cols.size() - 1; i >= 0; i--){
            if(cols[i] == col) return false;
            if(abs(cols[i] - col) == cols.size() - i) return false;
        }
        return true;
    }
    void search(int n, vector<int>& cols, vector<vector<string>>& result){
        if(cols.size() == n){
            result.push_back(drawResult(cols, n));
        }
        else{
            for(int i = 0; i < n; i++){
                if(isValid(cols, i, n)){
                    cols.push_back(i);
                    search(n, cols, result);
                    cols.pop_back();
                }
            }
        }
    }
    vector<string> drawResult(vector<int> cols,  int n){
        vector<string> res;
        for(int i = 0 ; i < n; i++){
            string tmp(n, '.');//注意一定是单引号
            tmp[cols[i]] = 'Q';
            res.push_back(tmp);
        }
        return res;
    }
};