poj 3254(状压DP)

poj 3254
状态压缩基础题。
题意是有一个矩阵，数为0的地方可以放牛，且牛不可以上下左右相邻，求摆放方案数。
DP解答，我们每行DP，但是这里状态比较复杂，这里要用到状压DP
设$dp(i, st[j])$为第$i$行使用状态$j$的方案数。
状态转移方程：
$$dp(i, st[j]) = \sum dp(i-1, st[k])$$
其中$k$是满足$k$在$i-1$行时与$j$在$i$行时不相邻的状态。
代码中运用了多处位运算技巧。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
using namespace std;
const int MAXN = 12 + 2;
int m, n;
int cur[MAXN], st[1<<MAXN], top, dp[MAXN][1<<MAXN];//输入状态,可行状态,可行状态个数,dp[i][st[j]]为第i行使用状态j的总方案.其中cur中1为不可放置, st中1为放置点 
bool fit(int j, int h) {return (st[j]&cur[h]) ? false : true;}
void clean() {
    top = 0, ms(cur, 0), ms(dp, 0); 
}
void solve() {
    clean();
    for (int i=0;i<(1<<n);i++) {//处理可行状态(无相邻) 
        if (i&(i>>1)) continue; else st[++top] = i;
    }
    for (int i=1;i<=m;i++) for (int j=1;j<=n;j++) {//处理输入 
        int x; scanf("%d", &x);
        if (!x) cur[i] += (1<<(j-1));
    }
    for (int i=1;i<=top;i++) if (fit(i, 1)) dp[1][i] = 1;//初始化DP 
    for (int hi=2;hi<=m;hi++) {//DP 
        for (int j=1;j<=top;j++) {
            if (!fit(j, hi)) continue;
            for (int k=1;k<=top;k++) {
                if (!fit(k, hi-1)) continue;
                if (st[j]&st[k]) continue;
                dp[hi][j] = (dp[hi][j] + dp[hi-1][k])%100000000;
            }
        }
    }
    int ans = 0;
    for (int i=1;i<=top;i++) ans = (ans+dp[m][i])%100000000;
    printf("%d\n", ans);
}
int main() {
    #ifndef ONLINE_JUDGE 
    freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
    #endif
    while (scanf("%d%d", &m, &n)==2) solve();
    return 0;
}