P1562 还是N皇后

wflengxuenong · 2022-09-25 16:36:10 · 个人记录

#include<iostream>
#include<stdio.h>
#include<cmath>
using namespace std;
int n,a[15];
int shu,ans;
int lowbit(int x) {
    return x&-x;
}
void dfs(int h,int l,int r,int p) {
    if(h==shu) {
        ans++;
        return;
    }
    int x=h|l|r|a[p];
    x=(~x)&shu;
    while(x) {
        int pi=lowbit(x);
        dfs(h|pi,(l|pi)>>1,(r|pi)<<1,p+1);
        x-=pi;
    }
}
int main() {
    cin>>n;
    for(int i=1; i<=n; i++) {
        string s;
        cin>>s;
        for(int j=0; j<n; j++) {
            if(s[j]=='.')a[i]|=(1<<(n-j-1));
        }
    }
    shu=(1<<n)-1;
    dfs(0,0,0,1);
    cout<<ans;
    return 0;
}