-
Notifications
You must be signed in to change notification settings - Fork 0
/
51. N-Queens.cpp
40 lines (40 loc) · 840 Bytes
/
51. N-Queens.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
#include<vector>
#include<math.h>
using namespace std;
class solution {
private:
vector<vector<string>> ret;
vector<int> queen;
public:
bool CheckPlace(int Checkline, int Checkrow) {
for (int i = 0; i < Checkline; i++) {
if (queen[i] == Checkrow || abs(Checkline - i) == abs(Checkrow - queen[i])) {
return false;
}
}
return true;
}
void PlaceQueen(int Checkline, int n) {
if (Checkline == n) {
vector<string> curr(n, string(n, '.'));
for (int i = 0; i < queen.size(); i++) {
curr[i][queen[i]] = 'Q';
}
ret.push_back(curr);
return;
}
else {
for (int i = 0; i < n; i++) {
if (CheckPlace(Checkline, i)) {
queen[Checkline] = i;
PlaceQueen(Checkline + 1, n);
}
}
}
}
vector<vector<string>> solveNQueens(int n) {
queen.resize(n);
PlaceQueen(0, n);
return ret;
}
};