C++数据结构与算法——回溯算法棋盘问题

C++第二阶段——数据结构和算法，之前学过一点点数据结构，当时是基于Python来学习的，现在基于C++查漏补缺，尤其是树的部分。这一部分计划一个月，主要利用代码随想录来学习，刷题使用力扣网站，不定时更新，欢迎关注！

一、 N 皇后

class Solution {
public:
    vector<vector<string>> result;
    vector<string>path;
    vector<vector<string>> solveNQueens(int n) {
        result.clear();
        vector<string> chessboard(n, string(n, '.')); // 初始化
        insertQ(n,0,chessboard);
        return result;
    }
    void insertQ(int n,int row,vector<string> chessboard){
        if(row==n){
            result.push_back(chessboard);
            return;
        }
        for(int col=0;col<n;col++){
            if(isValid(row,col,chessboard,n)){
                // 符合
                chessboard[row][col] ='Q';
                insertQ(n,row+1,chessboard);
                chessboard[row][col] = '.';
            }
        }
    }
    bool isValid(int row, int col, vector<string>& chessboard, int n) {
        // 检查列
        for (int i = 0; i < row; i++) { // 这是一个剪枝
            if (chessboard[i][col] == 'Q') {
                return false;
            }
        }
        // 检查 45度角是否有皇后
        for (int i = row - 1, j = col - 1; i >=0 && j >= 0; i--, j--) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }
        // 检查 135度角是否有皇后
        for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }
};

二、37. 解数独

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        insertBoard(board);
    }
    bool insertBoard(vector<vector<char>> &board){
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                if(board[i][j]!='.') continue;
                for(char k='1';k<='9';k++){
                    if(isValid(i,j,k,board)){
                        board[i][j] =k;
                        bool result =insertBoard(board);
                        if(result) return true;
                        board[i][j] = '.';
                    }
                }
                return false;
            }
        }
        return true;
    }
    bool isValid(int row, int col,char k,vector<vector<char>> board){
        // 1. 判断同行
        for(int i=0;i<9;i++){
            if(board[row][i]==k){
                return false;
            }
        }
        // 2.判断同列
        for(int j=0;j<9;j++){
            if(board[j][col]==k){
                return false;
            }
        }
        // 3. 判断小的九宫格
        int startX = (row/3)*3;
        int startY = (col/3)*3;
        for(int i=startX;i<startX+3;i++){
            for(int j=startY;j<startY+3;j++){
                if(board[i][j]==k){
                    return false;
                }
            }

        }
        return true;
    }
};