Luobuyu's Blog

0%

52.N皇后II

发表于 分类于 ， ， 热度： ℃ 评论：
本文字数： 861 阅读时长 ≈ 1 分钟
经典八皇后。

52.N 皇后 II

题目描述：

给一个整数 $ n $ ，返回解决方案的个数。

数据范围：
$ 1\le n\le 9 $

题解：

经典八皇后，注意打标记。打标记使用位运算，两个对角线一个是坐标和，一个是坐标差。记得把负的搞成正的。

代码：

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
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const static int INF = 0x3f3f3f3f;
    int ans = 0;

    void dfs(int step, int& n, vector<int> &vis)
    {
        if (step == n)
        {
            ans++;
            return;
        }
        // step 行，i 列
        for (int i = 0; i < n; ++i)
        {
            if (vis[0] & (1 << i))
                continue; // 0 表示列
            if (vis[1] & (1 << (i - step + n)))
                continue; // 1 表示 /*\*/
            if (vis[2] & (1 << (i + step)))
                continue; // 2 表示 /
            vis[0] |= (1 << i);
            vis[1] |= (1 << (i - step + n));
            vis[2] |= (1 << (i + step));
            dfs(step + 1, n, vis);
            vis[0] &= ~(1 << i);
            vis[1] &= ~(1 << (i - step + n));
            vis[2] &= ~(1 << (i + step));
        }
    }
    int totalNQueens(int n)
    {
        vector<int> vis(3, 0);
        dfs(0, n, vis);
        return ans;
    }
};