LeetCode52-N皇后 II

LeetCode52-N皇后 II

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
public int totalNQueens(int n) {
if (n < 1) return 1;
//初始化数组
queens = new int[n];
cols = new boolean[n];
left = new boolean[(n << 1) - 1];
right = new boolean[left.length];
place(0);
return way;
}

//定义存储皇后位置的数组 索引为row 列为元素值
int[] queens;
//标记某一列是否有皇后
boolean[] cols;
//标记左斜线是否有皇后
boolean[] left;
//标记右斜线是否有皇后
boolean[] right;
int way;

//在row位置放入皇后
void place(int row) {
if (row == queens.length) {
//到这里说明摆放完成增加次数
way++;
return;
}

for (int col = 0; col < cols.length; col++) {
if (cols[col]) continue;
int leftIndex = row - col + cols.length - 1;
if (left[leftIndex]) continue;
int rightIndex = row + col;
if (right[rightIndex]) continue;

//说明所处的位置没有皇后
//标记皇后
queens[row] = col;

//并且将当前所在的列 对角线都标记有皇后
cols[col] = true;
left[leftIndex] = true;
right[rightIndex] = true;
//进入下一行
place(row + 1);
//回溯
cols[col] = false;
left[leftIndex] = false;
right[rightIndex] = false;
}
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!