POJ - 1321 棋盤問題 n皇後問題(二進制版本)

POJ - 1321 棋盤問題 n皇後問題(二進制版本)

題目大意：給出一個n * n的棋盤，這個棋盤上面有些地方不能放棋子。
現在要求你在這個棋盤上面放置k個棋子，使得這些棋子的任意兩個不在同行同列上，問有多少種方法

解題思路：類似n皇後的問題，可以一行一行的處理，用二進制的1表示該位置可放，0表示不可放，All表示每行能放的狀態（ (1 << n) - 1）
假設列的狀態是s,那麼 s & (該行的限制) & All就是該行的終態了.
現在只要找到這個終態的所有1就可以了，那麼怎麼快速的找到這個1
假設終態是ss，那麼ss & (-ss) & All就是第一個1的位置了(可自行驗證)，然後設一個while循環就可以找到所有的1了，記得&All

#include
#include
using namespace std;
const int N = 20;
char str[N];
int n, k, ans, All, statu[N];

void init() {

    All = (1 << n) - 1;
    for(int i = 0; i < n; i++) {
        gets(str);
        statu[i] = All;
        for(int j = 0; j < n; j++)
            if(str[j] == '.')
                statu[i] ^= (1 << j);
    }
    ans = 0;
}

void solve(int cur, int num, int s) {
    if(num == k) {
        ans++;
        return ;
    }

    if(cur == n || n - cur + num < k) 
        return ;
    int ss = (s & statu[cur]) & All; 
    while(ss) {
        int t = ss & (-ss) & All;
        solve(cur + 1, num + 1, s ^ t);
        ss = (ss ^ t )& All;
    }
    solve(cur + 1, num, s);
}

int main() {
    while(gets(str)) {
        sscanf(str,"%d%d", &n, &k);
        if(n == -1 && k == -1)
            break;
        init();
        solve(0,0,All);
        printf("%d\n", ans);
    }
    return 0;
}