LeetCode N皇后 & N皇后 II

题目链接：https://leetcode-cn.com/problems/n-queens/

题目链接：https://leetcode-cn.com/problems/n-queens-ii/

题目大意：

　　略。

分析：

　　 https://blog.csdn.net/kai_wei_zhang/article/details/8033194。

代码如下：

 1 class Solution {
 2 public:
 3     int allOne;
 4     vector<vector<string>> ans;
 5     vector<string> ret;
 6     string tmp;
 7     int N;
 8     
 9     vector<vector<string>> solveNQueens(int n) {
10         allOne = (1 << n) - 1;
11         ans.clear();
12         tmp.assign(n, ‘.‘);
13         ret.assign(n, tmp);
14         N = n;
15         
16         solve(0, 0, 0, 0);
17         
18         return ans;
19     }
20     
21     // vd : 竖直方向
22     // ld : 左斜线方向
23     // rd : 右斜线方向
24     void solve(int level, int vd, int ld, int rd) {
25         if(level == N) {
26             ans.push_back(ret);
27             return;
28         }
29         
30         int limit = (vd | ld | rd) ^ allOne;
31         int pos;
32         
33         while(limit) {
34             pos = lowbit(limit);
35             limit = cutLowbit(limit);
36             
37             ret[level][N - __builtin_ffs(pos)] = ‘Q‘;
38             solve(level + 1, vd | pos, ((ld | pos) >> 1) & allOne, ((rd | pos) << 1) & allOne);
39             ret[level][N - __builtin_ffs(pos)] = ‘.‘;
40         }
41     }
42     
43     int lowbit(int x) {
44         return x & (-x);
45     }
46     
47     int cutLowbit(int x) {
48         return x & (x - 1);
49     }
50 };

View Code

 1 class Solution {
 2 public:
 3     int allOne;
 4     int ans;
 5     int N;
 6     
 7     int totalNQueens(int n) {
 8         allOne = (1 << n) - 1;
 9         ans = 0;
10         N = n;
11         
12         solve(0, 0, 0, 0);
13         
14         return ans;
15     }
16     
17     // vd : 竖直方向
18     // ld : 左斜线方向
19     // rd : 右斜线方向
20     void solve(int level, int vd, int ld, int rd) {
21         if(level == N) {
22             ++ans;
23             return;
24         }
25         
26         int limit = (vd | ld | rd) ^ allOne;
27         int pos;
28         
29         while(limit) {
30             pos = lowbit(limit);
31             limit = cutLowbit(limit);
32             
33             solve(level + 1, vd | pos, ((ld | pos) >> 1) & allOne, ((rd | pos) << 1) & allOne);
34         }
35     }
36     
37     int lowbit(int x) {
38         return x & (-x);
39     }
40     
41     int cutLowbit(int x) {
42         return x & (x - 1);
43     }
44 };

View Code