2010年1月13日星期三.sgu224
k皇后問(wèn)題的位運(yùn)算優(yōu)化
這個(gè)是基本上學(xué)過(guò)編程的人都會(huì)寫(xiě)過(guò)的程序。
但是對(duì)于這個(gè)NP問(wèn)題，只能搜索解決。如果寫(xiě)的不好的話(huà)很容易超時(shí)。
今天在Matrix67的文章中看到了使用位運(yùn)算的方法，本來(lái)我還想用dancing links來(lái)
搜一下呢，這個(gè)方法太精妙了！
傳送門(mén): http://www.matrix67.com/blog/archives/266
我們知道(x&-x)是求x的最低位1，而這個(gè)操作是非常快的。
在這個(gè)遞推過(guò)程中，只保存當(dāng)前行的不可行解，然后利用求反和上邊說(shuō)的求最低位1的方法對(duì)當(dāng)前
行的可行解進(jìn)行遍歷，然后遞推求解
不過(guò)這個(gè)不是n皇后問(wèn)題，是k皇后，所以還需要對(duì)算法進(jìn)行一些小小的改動(dòng)。
//http://www.shnenglu.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代表列的狀態(tài)，ld代表左對(duì)角線(xiàn)，rd代表右對(duì)角線(xiàn)，cnt是已經(jīng)使用的皇后數(shù)
//line是已經(jīng)推到了第幾第幾行
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;
}