leetcode 51 N 皇后
八皇后的题目已经很熟悉了，就是回溯的思想，具体说就是深度优先搜索
这里给出一种递归的写法:
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
| class Solution {
public:
void dfs(int map[], int cur, int &n, vector<vector<string>>& ret) {
if(cur >= n) {
vector<string> rr ;
for(int i = 0; i < n; i++) {
string curline;
for(int j=0;j<map[i];j++)
curline += ".";
curline += "Q";
for(int j=map[i]+1;j<n;j++)
curline += ".";
rr.push_back(curline);
}
ret.push_back(rr);
}
for(int i=0; i < n; i++) {
bool flag = false;
for(int j=0;j<cur;j++){
if(map[j] == i || abs(map[j] - i) == abs(cur-j)) {
flag = true;
break;
}
}
if(!flag) {
map[cur] = i;
dfs(map,cur+1,n, ret);
}
}
}
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> ret;
int map[n];
dfs(map, 0, n, ret);
return ret;
}
};
|
简单地说一下思路：
1. map 是一个一维的数组，但是可以用来记录二维的数据，map 的下标表示行号， map的值表示 列号, map[4]=3表示第4行、第3列防止一个皇后 2. dfs 是深度优先搜索 3. N 皇后的主要限制是横竖左右不得有其他皇后， map[j] == i || abs(map[j] - i) == abs(cur-j)，前面部分表示选取两行，这两行的皇后不得在同一列上；后面部分表示这两行的皇后不得在一个对角线上。
说下我遇到的坑： 1. 很久没写 c++，刚开始的结果不正确，以为是数组传参有问题，结果其实 c++ 里面的数组就是传指针，可以在函数内进行修改 2. N 皇后的判断条件把自己写糊涂了