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;
}
};