在家别憋坏了，写个题运动一下。
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
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
| class Solution {
int L[], R[], col[], row[];
List<List<String>> list = new ArrayList<>();
public void init(int n) {
L = new int[n + n];
R = new int[n + n];
col = new int[n];
row = new int[n];
}
public List<List<String>> solveNQueens(int n) {
init(n);
solve(0, n);
return list;
}
public void solve(int cur_row, int n) {
if(cur_row == n) {
List<String>cur_ans = new ArrayList<String>();
for(int i = 0; i < n; i++) {
StringBuilder sb = new StringBuilder();
for(int j = 0; j < row[i]; j++) sb.append(".");
sb.append("Q");
for(int j = row[i] + 1; j < n; j++) sb.append(".");
cur_ans.add(sb.toString());
}
list.add(cur_ans);
return ;
}
for(int i = 0; i < n; i++) {
if(col[i] == 0 && L[cur_row + i] == 0 && R[cur_row - i + n] == 0) {
row[cur_row] = i; col[i] = 1; L[cur_row + i] = 1; R[cur_row - i + n] = 1;
solve(cur_row + 1, n);
col[i] = 0; L[cur_row + i] = 0; R[cur_row - i + n] = 0;
}
}
}
}
|
