题解 | #N皇后问题#

class Solution {//参考大佬的Java代码，C++实现
public:
    /**
     * 
     * @param n int整型 the n
     * @return int整型
     */
    int Nqueen(int n) {//递归回溯
        // write code here
        vector<string> rst;
        vector<vector<char>> chess(n,vector<char>(n,'Z'));
        solve(rst, chess, 0, n);
        int len = rst.size();
        return len;
    }
    void solve(vector<string> &rst, vector<vector<char> > chess, int row, int n)
    {
        if(row == n) 
        {
            rst.emplace_back(convert(chess));
            return;
        }
        for(int col = 0; col < n; ++col)
        {
            if(valid(chess, row, col))
            {
                chess[row][col] = 'Q';
                solve(rst, chess, row+1, n);
                chess[row][col] = 'Z';
            }
        }
    }
    
    string convert(vector<vector<char> > chess) //就是放便可视化展示结果
    {
        string rst;
        int len = chess.size();
        for(int i = 0; i < len; ++i)
        {
            string *temp = new string(chess[i].begin(),chess[i].end());
            rst = rst + "\n"+ *temp;
        }
        return rst;
    }
    
    bool valid(vector<vector<char> > chess, int r, int c)
    {
        
        int col = chess[0].size();
        for(int i = r - 1 , j = c + 1; i >= 0 && j < col; i--, j++)//右上角
        {
            if(chess[i][j] ==  'Q') return false;
        }
        
        for(int i = r -1 , j = c -1; i >= 0 && j >= 0; i--, j--) //左上角
        {
            if(chess[i][j] == 'Q') return false;
        }
        for( int i = r-1; i >= 0; i--) //同一列
        {
            if(chess[i][c] == 'Q') return false;
        }
        return true;
    }
};