LeetCode/052_N-Queens_II.cpp at master · BellWind/LeetCode · GitHub

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
class Solution {
public:
    int totalNQueens(int n) {
        ans.clear();
        rv = vector<bool>(n, false);
        cv = vector<bool>(n, false);
        nd = vector<bool>(n * 2 - 1, false);
        bd = vector<bool>(n * 2 - 1, false);
        vector<string> tmp(n, string(n, '.'));
        nn = n;
        dfs(tmp, 0);
        return ans.size();
    }
private:
    vector<vector<string>> ans;
    vector<bool> rv, cv, nd, bd;
    int nn;
    bool Set(vector<string>& x, int r, int c) {
        if(rv[r] || cv[c] || bd[r + c] || nd[r - c + nn - 1])
            return false;
        rv[r] = cv[c] = bd[r + c] = nd[r - c + nn - 1] = true;
        x[r][c] = 'Q';
        return true;
    }
    void unSet(vector<string>& x, int r, int c) {
        x[r][c] = '.';
        rv[r] = cv[c] = bd[r + c] = nd[r - c + nn - 1] = false;
    }
    void dfs(vector<string>& cur, int k) {
        if(k == nn) {
            ans.push_back(cur);
            return ;
        }
        for(int i = 0; i < nn; i++) {
            if(Set(cur, k, i)) {
                dfs(cur, k + 1);
                unSet(cur, k, i);
            }
        }
    }
};