52. N-Queens II

第二題理論上比第一題還簡單,

只要算存在的個數就好了, 剩下的觀念跟第一題一模一樣

class Solution {
public:
    bool isValid(vector<string> &board, int row, int col){
        vector<vector<int>> dirs{{-1, -1}, {-1, 0}, {-1, 1}};
        for(auto dir: dirs){
            for(int i = row, j = col; i>= 0&& j >=0 && j < board.size();i+=dir[0], j += dir[1]){
                if(board[i][j] == 'Q'){
                    return false;
                }
            }
        }
        return true;
    }
    void backtrace(vector<string> &board, int row, int &res){
        if(row == board.size()){
            res++;
            return;
        }
        for(int col = 0; col < board.size(); col++){
            if(!isValid(board, row, col)){
                continue;
            }
            board[row][col] = 'Q';
            backtrace(board, row + 1, res);
            board[row][col] = '.';
        }
    }
    int totalNQueens(int n) {
        vector<string> board(n, string(n, '.'));
        int res = 0;
        backtrace(board, 0, res);
        return res;
    }
};