P1562 还是N皇后 – Xhesica's blog

链接:Miku

位运算的好题

（对于位运算本蒟蒻来说太毒瘤了）

对于这题的数据范围，把八皇后的代码改一改是不够的，必须要用位运算

先上代码

#include<cstdio>
#include<iostream>
#include<cstdio>
using namespace std;
int n,ans;
int map[25];
int end;
char c;
int sign; 
int lie;
int lowbit(int x){
    return x&(-x);
}
void dfs (int now,int l,int r,int deep)
 {
     if(now==end){
         ans++;
         return ;
     }
    int sign=end&(~(now|r|l|map[deep]));
    while(sign){
        int p=lowbit(sign);
        sign-=p;
        dfs(now+p,(l+p)<<1,(r+p)>>1,deep+1);
    }
}
int main()
{
    cin>>n;
    end=(1<<n)-1;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            cin>>c;
            if(c=='.')
                map[i]=map[i]|(1<<(n-j));
        }
    }
    dfs(0,0,0,1);
    cout<<ans;
    return 0;
}

首先呢，用一个数字的每一位代表一个位置的某种状态（放和不放）

然后

end=(1<<n)-1;

1表示全放上了，那么自然这个状态就是全放上了

void dfs (int now,int l,int r,int deep)
 {
     if(now==end){
         ans++;
         return ;
     }
    int sign=end&(~(now|r|l|map[deep]));
    while(sign){
        int p=lowbit(sign);
        sign-=p;
        dfs(now+p,(l+p)<<1,(r+p)>>1,deep+1);
    }
}

为什么又那么多参数呢，因为是位运算，我们完全可以把上一次的状态传下去，毕竟只是一个数，空间不大

（这也就意味着不需要回溯，因为我们直接传下去了）

既然我们用1表示已经放了，那么完全可以用这l（左对角线），r（右对角线）和now（竖着的限制）的与来找到能放的

为什么要取反呢，因为我们最后lowbit找的是最后一个1，不是0啊

但是又要和end&一下，因为~会把符号位取反

剩下的就显然了

发送评论 编辑评论

发送评论编辑评论