leetcode_cpp/recall/51.cpp

/*
 * @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; }