前言:

这段时间刚复习完dfs，然后在洛谷上用模板暴力解决了一道N皇后问题。

而当我想继续将N皇后问题一网打尽时，有一道N皇后问题直接让我TLE，让我这个蒟蒻不能AC这道题目。

而这道题恰好克制了朴素的dfs，也就是需要优化dfs。本蒟蒻花了好长时间看了代码终于弄懂了，也就是运用位运算优化了dfs

接下来让我来分享一下位运算这个常用的小算法。

概述：

下面介绍两个常用的位运算的函数（其实也不能称之为函数），都是针对为了表示二进制的数

求n的第k为数字：

1
n>>k&1;

返回n的第一位1二进制数:

1
2
3
int lowbit(x){
    return x&-x;
}

OK简单地介绍了一下位运算，接下来用实战来领悟得更透彻一些

实战

题目：还是N皇后

正如题目所说，这题是著名的N皇后问题。第一行有一个N。接下来有N行N列描述一个棋盘，“*”表示可放“.”表示不可放。输出方案数

位运算代码实现：

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
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x)&(-x))//定义一个宏实现lowbit
const int N=50;
char g[N][N];
int n,dg,udg,col;//dg,udg,col表示当前这一行N皇后放置位置的情况
int res,dep;//res记录方案数,dep表示当前是第几行
int f[N];//记录每一行初始状态下放置N皇后的情况
void dfs(int col,int dg,int udg,int dep){
    if(col==(1<<n)-1){
        res++;
        return ;
    }
    int s=((1<<n)-1)&~(col|dg|udg|f[dep]);//将改行可放置N皇后的地方&出来，
            // col|dg|udg|f[dep]将每一个不可放置的地方叠加起来，取反后&上((1<<n)-1)
     while(s){
         int w=lowbit(s);//先从最低位可放置N皇后的情况开始枚举
         dfs(col|w,(dg|w)<<1,(udg|w)>>1,dep+1);//col|w表示正下方无法放置N皇后
         //(dg|w)<<1表示正左下方不能放置，(udg|w)>>1表示正右下方不能放置;
         s-=w;//继续在这一行进行搜索是否有放置N皇后
     }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(cin>>g[i][j],g[i][j]=='.'){
                f[i]|=1<<n-j;//初始化每一行N皇后初始可放置的条件
            }
        }
    }
    dfs(0,0,0,1);
    cout<<res;
    return 0;
}