forked from tugayac/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
N-Queens II.cpp
49 lines (40 loc) · 1.05 KB
/
N-Queens II.cpp
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
int result, bound;
void setmask(vector<int> &mask, int step, int pos){
int len = mask.size();
for (int i = step+1; i != len; i++){
mask[i] |= 1 << pos;
}
int lb = max((int)0, 0 - min(pos, step)), ub = len - max(step, pos);
for (int i = lb; i != ub; i++){
mask[step+i] |= 1 << (pos + i);
}
for (int i = -13; i != 14; i++){
if (step-i < len && step-i>-1 && pos+i < len && pos + i > -1)
mask[step-i] |= 1 << (pos + i);
}
return ;
}
int search(vector<int> & mask, int step, int sz){
if (step == sz){
return 1;
}
int x = 0;
for (int i = 0; i != sz; i++){
if (!(1<<i & mask[step])){
vector<int> tmp = mask;
setmask(tmp, step, i);
x += search(tmp, step + 1, sz);
}
}
return x;
}
class Solution {
public:
int totalNQueens(int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
result = 0;
vector<int> mask(n);
return search(mask, 0, n);
}
};