leetcode/N-Queens.cpp at master · lccycc/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
42
43
44
45
46
class Solution {
public:
    vector<int> row;
    vector<bool> slp, slm;
    vector<vector<string> > res;
    void dfs(int n, int k){
        if (k>=n){
            vector<string> tmp;
            for (int i = 0; i<n; i++){
                string s;
                for (int j = 0; j<row[i]; j++) s += '.';
                s += 'Q';
                for (int j = row[i]+1; j<n; j++) s += '.';
                tmp.push_back(s);
            }
            res.push_back(tmp);
            return ;
        }
        for (int i = k; i<n; i++){
            int x = row[i];
            if (slm[x-k+n] || slp[x+k] ){
                continue;
            }
            swap(row[k], row[i]);
            slm[x-k+n] = slp[x+k] = true;
            dfs(n, k+1);
            slm[x-k+n] = slp[x+k] = false;
            swap(row[k], row[i]);
        }
    }

    vector<vector<string> > solveNQueens(int n) {
        row.clear();
        slp.clear();
        for (int i = 0; i<n+n; i++){
            slp.push_back(0);
        }
        slm = slp;
        for (int i = 0; i<n; i++){
            row.push_back(i);
        }
        res.clear();
        dfs(n, 0);
        return res;
    }
};