-
Notifications
You must be signed in to change notification settings - Fork 0
/
NQueens.cpp
61 lines (57 loc) · 1.94 KB
/
NQueens.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
50
51
52
53
54
55
56
57
58
59
60
61
// https://oj.leetcode.com/problems/n-queens/
class Solution {
public:
vector<vector<string> > solveNQueens(int n) {
_result.clear();
_empty_line.assign(n, '.');
vector<string> cur_map;
_try_level(cur_map, n);
return _result;
}
void show() {
for (vector<vector<string> >::const_iterator iter = _result.begin();
iter != _result.end(); ++iter) {
cout << "=========================================" << endl;
for (vector<string>::const_iterator line_iter = iter->begin();
line_iter != iter->end(); ++line_iter)
{
cout << "\t" << *line_iter << endl;
}
}
}
private:
void _try_level(vector<string> cur_map, int n) {
for (int i = 0; i < n; ++i) {
string cur_line = (i > 0 ? _empty_line.substr(0, i) : "")
+ "Q" + ((i < n - 1) ? _empty_line.substr(i + 1, n - i - 1) : "");
size_t cur_size = cur_map.size();
bool enable = true;
for (int j = 0; j < cur_size; ++j) {
int gap = cur_size - j;
if ('Q' == cur_map.at(j).at(i)) {
enable = false;
break;
}
if ((i - gap >= 0) && ('Q' == cur_map.at(j).at(i - gap))) {
enable = false;
break;
}
if ((i + gap < n) && ('Q' == cur_map.at(j).at(i + gap))) {
enable = false;
break;
}
}
if (enable) {
cur_map.push_back(cur_line);
if (n == cur_map.size()) {
_result.push_back(cur_map);
} else {
_try_level(cur_map, n);
}
cur_map.pop_back();
}
}
}
vector<vector<string> > _result;
string _empty_line;
};