Keshawn_lu's Blog

Leetcode 51. N 皇后

字数统计: 581阅读时长: 2 min
2020/09/03 Share

题目简介:

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 皇后问题存在两个不同的解法。

提示:

  • 皇后彼此不能相互攻击,也就是说:任何两个皇后都不能处于同一条横行、纵行或斜线上。

思路:

又是深搜+回溯的做法,一行一行来放皇后,对于每行,遍历每列的位置,对于每个位置,进行下列判断:

  1. 该列在之前的行上是否已有皇后(只需关心之前的行即可,因为是逐行放皇后的)。
  2. 在45度和135度角的斜行上,是否已有皇后(同样只需关心之前的行即可)。

当遍历完n行时,即row == n,此时便为一个答案,加入答案数组即可。

tip:

  • 注意chess数组的初始化。

代码如下:

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;
}

//判断45度角, 只需要判断之前行数的就行了
for(int i = row - 1, j = col + 1; i >= 0 && j < chess.size(); i--, j++){

if(chess[i][j] == 'Q')
return false;
}

//判断135度角
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;
}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: