2010年1月13日星期三.sgu224
k皇后问题的位运算优化
这个是基本上学过编程的人都会写过的程序。
但是对于这个NP问题，只能搜索解决。如果写的不好的话很容易超时。
今天在Matrix67的文章中看到了使用位运算的方法，本来我还想用dancing links来
搜一下呢，这个方法太精妙了！
传送门: http://www.matrix67.com/blog/archives/266
我们知道(x&-x)是求x的最低位1，而这个操作是非常快的。
在这个递推过程中，只保存当前行的不可行解，然后利用求反和上边说的求最低位1的方法对当前
行的可行解进行遍历，然后递推求解
不过这个不是n皇后问题，是k皇后，所以还需要对算法进行一些小小的改动。
//http://www.cppblog.com/schindlerlee/
typedef long long LL;
const int N = 16;
int n, k;
#define bin(x) (1 << (x))
#define L(x) ((x) << 1)
#define R(x) ((x) >> 1)
#define low(x) ((x) & -(x))
int res = 0, full;
//row代表列的状态，ld代表左对角线，rd代表右对角线，cnt是已经使用的皇后数
//line是已经推到了第几第几行
void dfs(int row, int ld, int rd, int cnt, int line)
{
int p, t;
if (line < n && cnt < k) {
t = full & ~(row | ld | rd);
while (t != 0) {
p = low(t);
t ^= p;
dfs(row + p, L(ld + p), R(rd + p), cnt + 1, line + 1); //下一行
}
dfs(row, L(ld), R(rd), cnt, line + 1); //此行空
} else if(cnt == k){
res++;
}
}
int main()
{
int i, j;
scanf("%d%d", &n, &k);
full = bin(n) - 1;
dfs(0, 0, 0, 0, 0);
printf("%d\n", res);
return 0;
}