题目简介：
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例：
1
2
3
4
5
6
7
8
9
10
11
12
13
| 输入：4
输出：[
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。
|
提示：
- 皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。
思路：
又是深搜+回溯的做法，一行一行来放皇后，对于每行，遍历每列的位置，对于每个位置，进行下列判断：
- 该列在之前的行上是否已有皇后(只需关心之前的行即可，因为是逐行放皇后的)。
- 在45度和135度角的斜行上，是否已有皇后(同样只需关心之前的行即可)。
当遍历完n行时，即row == n，此时便为一个答案，加入答案数组即可。
tip:
代码如下：
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
62
| class Solution {
public:
vector<vector<string>> res;
void dfs(vector<string>& chess, int n, int row){
if(row == n){
res.push_back(chess);
return;
}
for(int col = 0; col < n; col++){
if(judge(chess, row, col)){
chess[row][col] = 'Q';
dfs(chess, n, row + 1);
chess[row][col] = '.';
}
}
}
bool judge(vector<string>& chess, int row, int col){
for(int i = 0; i < row; i++){
if(chess[i][col] == 'Q')
return false;
}
for(int i = row - 1, j = col + 1; i >= 0 && j < chess.size(); i--, j++){
if(chess[i][j] == 'Q')
return false;
}
for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--){
if(chess[i][j] == 'Q')
return false;
}
return true;
}
vector<vector<string>> solveNQueens(int n) {
vector<string> chess(n, string(n, '.'));
dfs(chess, n, 0);
return res;
}
};
|
