123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354 |
- /*
- * @Description:
- * @Version: 1.0
- * @Autor: zhuyijun
- * @Date: 2021-11-11 22:23:35
- * @LastEditTime: 2021-11-11 23:05:48
- */
- #include <bits/stdc++.h>
- using namespace std;
- vector<vector<string>> res;
- bool isVaild(vector<string> &board, int row, int col) {
- int n = board.size();
- // 检查列
- for (int i = 0; i < row; i++) {
- if (board[i][col] == 'Q') {
- return false;
- }
- }
- // 检查 45度角是否有皇后
- for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
- if (board[i][j] == 'Q') {
- return false;
- }
- }
- // 检查 135度角是否有皇后
- for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
- if (board[i][j] == 'Q') {
- return false;
- }
- }
- return true;
- }
- void backtrack(vector<string> &board, int row) {
- if (row == board.size()) {
- res.push_back(board);
- return;
- }
- auto result = board[row];
- for (int col = 0; col < result.size(); col++) {
- if (!isVaild(board, row, col)) {
- continue;
- }
- board[row][col] = 'Q';
- backtrack(board, row + 1);
- board[row][col] = '.';
- }
- }
- vector<vector<string>> solveNQueens(int n) {
- vector<string> board(n, string(n, '.'));
- backtrack(board, 0);
- return res;
- }
- int main() { return 0; }
|