洛谷1562 还是N皇后

看到是蓝题我就知道不可能是那道黄题的做法了，不过还是打了个暴力，无氧60，吸氧70

bool mp[16][16],vis[16],vis2[32],vis3[32]; //x-y+14;x+y
int n,m,a,b,c,ans;

void dfs(int x)
{
    if (x==n+1)
    {
        ans++;
        return;
    }
    for (int i=1;i<=n;i++)
    {
        if (!mp[x][i] || vis[i] || vis2[i-x+14] || vis3[i+x]) continue;
        vis[i]=vis2[i-x+14]=vis3[i+x]=1;
        dfs(x+1);
        vis[i]=vis2[i-x+14]=vis3[i+x]=0;
    }
    return;
}

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        char s[16];
        scanf("%s",s);
        int len=strlen(s);
        for (int j=0;j<len;j++)
        {
            if (s[j]=='*') mp[i][j+1]=1;
            else mp[i][j+1]=0;
        }
    }
    dfs(1);
    printf("%d",ans);
    return 0;
}

看了题解才知道是位运算，我还是太菜了。

本质其实就是用0来代表下一行可以放棋子的位置，横纵很好解决，两条对角线又刚好可以表示成左移和右移一位，每次把几种约束条件取个∪就行了。

剩下的就是枚举dfs了，而枚举0又不太方便，所以直接取反后用lowbit枚举1即可。

int n,m,ans,mp[16];

inline int lowbit(int x)
{
    return x&-x;
}

void dfs(int x,int cnt,int l,int r)
{
    if (x==m)
    {
        ans++;
        return;
    }
    int now=m&(~(mp[cnt]|l|r|x));
    while (now)
    {
        int lbt=lowbit(now);
        now-=lbt;
        dfs(x+lbt,cnt+1,(l+lbt)>>1,(r+lbt)<<1);
    }
    return;
}

int main()
{
    scanf("%d",&n);
    m=(1<<n)-1;
    for (int i=1;i<=n;i++)
    {
        char s[16];
        scanf("%s",s);
        for (int j=0;j<n;j++)
        {
            if (s[j]=='*') continue;
            mp[i]|=1<<(n-j-1);
        }
    }
    dfs(0,1,0,0);
    printf("%d",ans);
    return 0;
}