1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| class Solution {
public:
int totalNQueens(int n) {
this->n = n;
total = 0;
only_col.resize(n);
row_minus_col.resize((n << 1) - 1);
row_plus_col.resize((n << 1) - 1);
totalNQueens_helper(0);
return total;
}
private:
void totalNQueens_helper(int row) {
if (row == n) {
++total;
return;
}
for (int col(0); col < n; ++col) {
if (!only_col[col] && !row_minus_col[n - 1 + row - col] && !row_plus_col[row + col]) {
only_col[col] = row_minus_col[n - 1 + row - col] = row_plus_col[row + col] = true;
totalNQueens_helper(row + 1);
only_col[col] = row_minus_col[n - 1 + row - col] = row_plus_col[row + col] = false;
}
}
}
int total;
int n;
vector<bool> only_col;
vector<bool> row_minus_col;
vector<bool> row_plus_col;
};
|