-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSolution_51.java
More file actions
59 lines (54 loc) · 1.49 KB
/
Solution_51.java
File metadata and controls
59 lines (54 loc) · 1.49 KB
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
package com.hilbert25.leetcode;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.List;
/**
* @author : hilbert25
* @version 创建时间：2017年4月13日 下午7:54:32 LeetCode com.hilbert25.leetcode
* Solution_51
*/
public class Solution_51 {
public static void main(String[] args) {
// TODO Auto-generated method stub
solveNQueens(4);
}
public static List<List<String>> solveNQueens(int n) {
List<List<String>> res = new ArrayList<List<String>>();
if (n == 0) {
res.add(new ArrayList<String>());
return res;
}
BitSet col = new BitSet(n);
BitSet left = new BitSet(2 * n - 1);
BitSet right = new BitSet(2 * n - 1);
List<String> temp = new ArrayList<String>(n);
search(res, temp, col, left, right, 0, n);
return res;
}
public static void search(List<List<String>> res, List<String> temp, BitSet col, BitSet left, BitSet right, int cur,
int n) {
if (cur == n) {
res.add(new ArrayList<>(temp));
return;
}
for (int i = 0; i < n; i++) {
if (!col.get(i) && !left.get(cur - i + n - 1) && !right.get(cur + i)) {
char[] cArr = new char[n];
Arrays.fill(cArr, '.');
cArr[i] = 'Q';
temp.add(String.copyValueOf(cArr));
col.set(i, true);
left.set(cur - i + n - 1, true);
right.set(cur + i, true);
cur++;
search(res, temp, col, left, right, cur, n);
cur--;
col.set(i, false);
left.set(cur - i + n - 1, false);
right.set(cur + i, false);
temp.remove(cur);
}
}
}
}