leetcode

51.N皇后

力扣链接

class Solution {
public:
    std::vector<std::vector<std::string>> res;
    void backtracking(int n, int row, std::vector<std::string>&chessboard){
        if (row==n){
            res.push_back(chessboard);
            return;
        }
        for (int col=0; col<n; col++){
            if (isvalid(row, col, chessboard, n)){
                chessboard[row][col] = 'Q';
                backtracking(n, row+1, chessboard);
                chessboard[row][col] = '.';
            }
        }
    }

    bool isvalid(int row, int col, std::vector<std::string>&chessboard, int n){
        // 检查正上方
        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;
    }

    std::vector<std::vector<string>> solveNQueens(int n) {
    std::vector<std::string> chessboard(n, std::string(n, '.'));
    backtracking(n, 0, chessboard);
    return res;
    }
};