【LetMeFly】51.N皇后
力扣题目链接：https://leetcode.cn/problems/n-queens/
n 皇后问题 研究的是如何将n个皇后放置在n×n的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数n，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个不同的 n 皇后问题的棋子放置方案，该方案中'Q'和'.'分别代表了皇后和空位。
笔者注：
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子
这个可能一些中国小朋友不知道，因此已经在Github提交issue啦
示例 1:
1
2
3
| 输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。
|
示例 2:
提示:
题目大意
给你一张n×n的棋盘，让你往上放置n个皇后。这些皇后满足：任意两皇后不在同一行、不在同一列、不在同一斜线上。
思路
我们可以定义一个函数goon(int line)，来在当前棋盘状态下，继续往第line行落子。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| void goon(int line) {
如果已经放满了：
说明当前状态是一个可行的最终状态
当前棋盘加入答案、结束递归
否则：
遍历这一行所有位置，看每个位置是否能放
对于某个位置：
如果能放：
就放一个“皇后”
继续递归模拟下一行
模拟结束后撤销这个皇后，判断下一个位置是否可行
否则：
不做操作，继续判断下一个位置
}
|
至于上文中的“判断一个位置是否能放”，实现方法为：
1
2
3
4
5
6
7
8
9
10
| bool ifOk(int x, int y) {
遍历这一行，如果已有皇后，就返回false
遍历这一列，如果已有皇后，就返回false
接下来是对角线上的位置。同一正对角线上的元素满足“横坐标-纵坐标值相等”，同一负对角线上的元素满足“横坐标+纵坐标值相等”。
遍历每一行，求出这一行中和(x, y)位于同一对角线上的位置，如果已有皇后，就返回false
如果前面都没有返回false，说明这是一个合法的位置，就return true;
}
|
方法一：回溯
思路中已经描述地差不多了，接下来就是具体实现可参考代码注释
AC代码
C++
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
| class Solution {
private:
vector<string> a;
vector<vector<string>> ans;
int n;
bool ifOk(int x, int y) {
for (int j = 0; j < n; j++) {
if (a[x][j] == 'Q') {
return false;
}
}
for (int i = 0; i < n; i++) {
if (a[i][y] == 'Q') {
return false;
}
}
for (int i = 0; i < n; i++) {
int j = x + y - i;
if (j >= 0 && j < n && a[i][j] == 'Q') {
return false;
}
j = i - x + y;
if (j >= 0 && j < n && a[i][j] == 'Q') {
return false;
}
}
return true;
}
void goon(int line) {
if (line >= n) {
ans.push_back(a);
return;
}
for (int j = 0; j < n; j++) {
if (ifOk(line, j)) {
a[line][j] = 'Q';
goon(line + 1);
a[line][j] = '.';
}
}
}
public:
vector<vector<string>> solveNQueens(int n) {
this->n = n;
string oneLine(n, '.');
for (int i = 0; i < n; i++) {
a.push_back(oneLine);
}
goon(0);
return ans;
}
};
|
同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/124999635