2011-06-16 18:15:54Morris
d757. 11195 - Another n-Queen Problem
內容 ：
相 信n-Queen問題對每個研究backtracking的人來講都不陌生，這個問題是要在一個n*n大小的棋盤上擺n個皇后，讓她們不會互相攻擊到。為 了讓這個問題更難一點，我們設計了一些障礙物在棋盤上，在這些點上不能放皇后。請留意這些障礙物並不會防止皇后被攻擊。
在傳統的8-Queen問題中，旋轉與鏡射被視為不同解法，因此我們有92種可能的方式來放置皇后。
輸入說明
：
輸入的資料最多包含10筆測試個案，每個測試個案的第一行會有一個整數n（3 < n < 15），接下來的n行代表棋盤資料，點號'.'代表空的盤格，星號'*'代表放有障礙物的盤格。0代表測資結束，請不要對0做任何輸出。
輸出說明
：
對每筆測試個案，輸出這是第幾個case以及這個case有幾種可能的放置方式。
範例輸入 ：
8 ........ ........ ........ ........ ........ ........ ........ ........ 4 .*.. .... .... .... 0
範例輸出 ：
Case 1: 92 Case 2: 1
提示
：
據說有種叫做"Bitmask"的東西。
Luckycat譯。
出處
：
11195 - Another n-Queen Problem
(管理：asas)
作法&說明 : http://maplewing.blogspot.com/2011/03/uva11195another-n-queen-problem.html
下面只是仿打，可忽略
bitmask太強大了，壓縮到數字中用運算元去做運算
作法&說明 : http://maplewing.blogspot.com/2011/03/uva11195another-n-queen-problem.html
下面只是仿打，可忽略
bitmask太強大了，壓縮到數字中用運算元去做運算
/**********************************************************************************/
/* Problem: d757 "11195 - Another n-Queen Problem" from 11195 - Another n-Queen Problem*/
/* Language: C */
/* Result: AC (628ms, 260KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-16 12:37:03 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
int y_row[16], Ans;
void backtracking(int n, int y, int x, int slash1, int slash2) {
if(y == n) {Ans++; return ;}
int nowslash1 = slash1 >> y;
int nowslash2 = slash2 >> (n-y-1);
int judge = y_row[y] & x & nowslash1 & nowslash2;
int xput;
while(judge) {
xput = judge & (-judge); /*lowbit*/
backtracking(n, y+1, x^xput, slash1^(xput<<y), slash2^(xput<<(n-y-1)));
judge ^= xput;
}
}
main() {
int n, C = 0, a, b;
char s[16];
while(scanf("%d", &n) == 1 && n) {
for(a = 0; a < n; a++) {
scanf("%s", s);
y_row[a] = (1<<n)-1;
for(b = 0; b < n; b++)
if(s[b] == '*')
y_row[a] ^= (1 << b);
}
Ans = 0;
backtracking(n, 0, (1<<n)-1, (1<<(2*n-1))-1, (1<<(2*n-1))-1);
printf("Case %d: %d\n", ++C, Ans);
}
return 0;
}