12.11 log

51. N皇后

class Solution {
private:
    vector<vector<string>> result;
    void backtracking(int n,int row,vector<string>& chessBoard){
        if(row==n){
            result.push_back(chessBoard);
            return;
        }
        for(int i=0;i<n;i++){
            if(isValid(n,row,i,chessBoard)){
                chessBoard[row][i]='Q';
                backtracking(n,row+1,chessBoard);
                chessBoard[row][i]='.';
            }
        }
        return;
    }
public:
    bool isValid(int n,int row,int col,vector<string>& chessBoard){
        for(int i=0;i<row;i++){
            if(chessBoard[i][col]=='Q') return false;
        }
        for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--){
            if(chessBoard[i][j]=='Q') return false;
        }
        for(int i=row-1,j=col+1;i>=0&&j<n;i--,j++){
            if(chessBoard[i][j]=='Q') return false;
        }
        return true;
    }
    vector<vector<string>> solveNQueens(int n) {
        result.clear();
        vector<string> chessBoard(n,string(n,'.'));
        backtracking(n,0,chessBoard);
        return result;
    }
};

递归的参数为皇后的个数，递归的行数，创建的棋盘，递归的返回值无；递归的终止条件为当递归的层数到达n层时，result记录该棋盘并返回，就相当于记录叶子节点；单层递归逻辑为用for循环横向遍历，横向遍历的宽度为n，row表示递归的深度，和之前一些题目startIndex类似，进入for循环先判断是否符合要求，如符合要求chessBoard[row][i]=‘Q’,直接进入下一层递归，递归之后在回溯，chessBoard[row][i]=‘.’。判断是否符合要求的函数，可以适当剪枝，只用考虑该位置同一列，上面部分否有'Q'，以及该位置上半部分左右两斜线上是否有'Q'。result数据结构与要返回的数据结构相同，棋盘二维数组的初始化方式与一维数组初始化方式相同。