leetcode

0 class Solution {

1 vector<string> board;

2 unordered_set<int> used;

3 int n, res;

4

5 bool valid(int row, int col) { return row >= 0 && row < n && col >= 0 && col < n; }

6

7 bool safe(int row, int col) {

8 static vector<pair<int, int>> ofsts = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};

9

10 if (used.count(col)) return false;

11 for (auto &ofst : ofsts) {

12 int a = row + ofst.first, b = col + ofst.second;

13 while (valid(a, b)) {

14 if (board[a][b] == 'Q') return false;

15 a += ofst.first, b += ofst.second;

16 }

17 }

18 return true;

19 }

20

21 void rec(int row) {

22 if (row == n) {

23 res++;

24 return;

25 }

26

27 for (int i = 0; i < n; i++) {

28 if (!safe(row, i)) continue;

29 used.insert(i);

30 board[row][i] = 'Q';

31 rec(row + 1);

32 used.erase(i);

33 board[row][i] = '.';

34 }

35 }

36

37 public:

38 int totalNQueens(int n) {

39 this->n = n;

40 board = vector<string>(n, string(n, '.'));

41 rec(0);

42 return res;

43 }

44 };