题解 P1562 【还是N皇后】

karma · 2017-11-06 09:45:38 · 题解

此题是一个练习位运算的好题

由于楼下题解解释过少,我来进行补充.

其实此题的正解就是位运算,用其他方法会TLE(打表除外)

分析:

• 逐行放置皇后,首先排除每行有多个皇后互相排斥的情况

• 用二进制表示状态.1表示该点不能放(与其他位置的皇后排斥或初始状态就不能放).0表示该点可以放皇后

• 用sta[]来存储初始状态,将'.'位 置为1

• dfs保存四个参数:当前行的状态,从左上到右下对角线的状态,从右上到左下对角线的状态,当前为第几行

• 获取当前哪一位可以放置皇后:将四者取并集(即将四者进行或运算).得到的状态中为0的就可以放置皇后.

• 为了快速得到可以放置皇后的位置,对上一步得到的状态进行取反.转换成快速得到1的位置.

• 用树状数组中的lowbit()就可以得到从右向左的第一个1

• 将状态中的1减掉,继续找下一个1

• 更新"将是下一行的状态",由于对角线是斜着影响的,所以左上到右下对角线的状态需要左移一位,右上到左下对角线的状态需要右移一位.

• 知道当前行的状态全为1时,即每一行都有一个皇后时,ans++;

#include<cstdio>
#define xianzhi ~(now|ld|rd|sta[d])
#define lowbit(pos)  pos&-pos
#define youzuo (ld+p)<<1
#define zuoyou (rd+p)>>1
int n,all,sta[25],ans;
void dfs(int now,int ld,int rd,int d){//now这个状态限制的是"列之间的冲突" 
    if(now==all){ans++;return ;}
    int pos=all&xianzhi,p;
    while(pos){
        p=lowbit(pos);
        pos-=p;
        dfs(now+p,youzuo,zuoyou,d+1);
    }
}
int main(){
    scanf("%d",&n);
    all=(1<<n)-1;//最终状态(即全部放完的状态) 
    char c[20]; 
    for(int i=1;i<=n;++i){
        scanf("%s",c+1);
        getchar();//消除行末回车 
        for(int j=1;j<=n;++j){
            if(c[j]=='.')sta[i]|=(1<<(n-j));//将sta[i]的"第j位"置为1 
        }
    }
    dfs(0,0,0,1);
    printf("%d",ans);
    return 0;
}