题目描述
有一个N*N的棋盘，有些格子可以放置皇后，一个皇后可以对它这一行的位置，这一列的位置，它所在的左对角线和右对角线攻击，这些位置不能放置皇后，一共放置N个皇后，问有多少种放置的方式。
输入输出格式
输入格式：
第一行有一个N。接下来有N行N列描述一个棋盘，“*”表示可放“.”表示不可放。
输出格式：
输出方案总数
solution
这道题主要考察位运算，例如101001表示这一排第2、4、5个位置可以放置皇后。
我们用k进制(这里是二进制)来存储状态，这也是状态压缩的基本思想。
显然每行只能放置一个皇后，我们逐行枚举
那么我们需要记录四个状态，一是这一行题目给定的状态，二是这一行中有哪些列会被之前摆放的皇后攻击，那么无法再摆放，三是左对角线的影响，四是右对角线的影响，这些状态只用每行一个数字的二进制来存储就行了。
判断时将这四种情况取并集，再取反，1的位置就成了可以放置的位置，利用lowbit进行DFS即可，具体的实现细节还要看代码
code
#include<cstdio>
#include<iostream>
#include<
string>
#define re register
using namespace std;
int n,all,sta[
50],ans;
string s;
int lowbit(
int x)
//找到最右边的1位
{
return x&-
x;
}
//取反是补码，与反码不同 ~(3)=-4;
void dfs(
int now,
int L,
int R,
int d)
{
if(now==all){ans++;
return;}
//当now==all的时候，说明全部摆放完毕,ans++
//now表示到这一行的摆放情况,L表示左对角线的情况
//R表示右对角线的情况,d记录现在在哪一行，
//sta[d]表示第d行题目的限制条件
int pos=all&(~(now|L|R|sta[d])),p;
//all是用来限制，把右对角线左移移出去的除掉
while(pos)
//枚举每个可以放的位置
{
p=
lowbit(pos);
pos-=p;
//这一个位置即将枚举，删掉
dfs(now+p,(L+p)>>
1,(R+p)<<
1,d+
1);
//左对角线对下一行的影响是它的左下角，因此二进制右移
//右对角线相反,别忘了加上p处放置的棋子的影响
}
}
int main()
{
scanf("%d",&
n);
all=(
1<<n)-
1;
//表示最终状态，比如 n=4 01111
for(re
int i=
1;i<=n;++
i)
{
cin>>
s;
for(
int j=
1;j<=n;++
j)
if(s[j-
1]==
'.')sta[i]|=(
1<<(n-j));
//对这个数二进制每个位置进行操作
}
dfs(0,
0,
0,
1);
//一开始没放，没有任何摆放过皇后限制
printf(
"%d",ans);
return 0;
}
转载于:https://www.cnblogs.com/Liuz8848/p/10796167.html
相关资源：N皇后问题(位运算，C语言版)
