leetcode

0 class Solution {

1 vector<vector<string>> res;

2 vector<string> board;

3 unordered_set<int> used;

4 int n;

5

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

7

8 bool safe(int row, int col) {

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

10

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

12 for (auto &ofst : ofsts) {

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

14 while (valid(a, b)) {

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

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

17 }

18 }

19 return true;

20 }

21

22 void rec(int row) {

23 if (row == n) {

24 res.push_back(board);

25 return;

26 }

27

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

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

30 used.insert(i);

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

32 rec(row + 1);

33 used.erase(i);

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

35 }

36 }

37

38 public:

39 vector<vector<string>> solveNQueens(int n) {

40 this->n = n;

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

42 rec(0);

43 return res;

44 }

45 };