52. N-Queens II

发表于 | 分类于

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

解法1： DFS

这题比要print所有的解法的一个可以优化的地方是，只需要不停的每行fill的同时check是否是valid,如果是就继续往下填。
在看是否是合法的时候用三个数组或者是set来保存当前fill的状态。

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
class Solution {
    int count = 0;
    public int totalNQueens(int n) {
        Set<Integer> cols = new HashSet<>();
        Set<Integer> rightDiag = new HashSet<>();
        Set<Integer> leftDiag = new HashSet<>();
        solve(0, cols, rightDiag, leftDiag, n);
        return count;
    }
    private void solve(int row, Set<Integer> cols, Set<Integer> rightDiag, Set<Integer> leftDiag, int n) {
        if (row == n) {
            count++;
            return;
        }
        /*
            Fill in each row
            And check if it is valid  
        */
        for (int i = 0; i < n; i++) {
            if (cols.contains(i)) continue;
            if (rightDiag.contains(row - i)) continue;
            if (leftDiag.contains(row + i)) continue;
            cols.add(i);
            rightDiag.add(row - i);
            leftDiag.add(row + i);
            solve(row + 1, cols, rightDiag, leftDiag, n);
            cols.remove(i);
            leftDiag.remove(row + i);
            rightDiag.remove(row - i);
        }
        return;
    }
}