poj 3254(状态压缩+动态规划)

http://poj.org/problem?id=3254

题意：有一个n*m的农场（01矩阵），其中1表示种了草可以放牛，0表示没种草不能放牛，并且如果某个地方放了牛，它的上下左右四个方向都不能放其他的牛，

问总共有多少种放牛方案？？（不放也是一种方案）

状态压缩讲的好的博客

分析：利用状态压缩进行求解，先筛选出每行所有的可能状态，然后将每行与所有可行状态进行比较。

dp[i][j]表示当第i行的状态为j时前i行的放牛方案总数。

所以状态转移方程便是 dp[i][j] = dp[i][j]+dp[i-1][t] //t代表第i-1行所有符合条件的状态数。

最后的结果为 sum(dp[n][i]) ..数组开小了，不停WA

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define N 12
#define mod 100000000
using namespace std;
int dp[N+1][1<<N];  ///dp[i][j]表示当第i行的状态为j时前i行的放牛方案总数
int state[1<<N]; ///保存所有的合法状态数
int cur[N+1]; ///每一行的状态,注意这里保存的是0,因为当我们保存0时,如果某一状态与当前行相与不为0，那么
///就能判断出那个状态是不合法的(假设那个位置不应该种草，而它种了草)
int n,m;
bool check(int k){
    if(k&(k<<1)) return false;
    return true;
}
void init(int &k){
    for(int i=0;i<(1<<m);i++){
        if(check(i)) state[++k]=i;
    }
    //printf("%d
",k);
}

int main()
{
    while(scanf("%d%d",&n,&m)!=EOF){
        int k = 0;
        init(k);
        int num;
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++){
            cur[i]=0;
            for(int j=1;j<=m;j++){
                scanf("%d",&num);
                if(num==0) cur[i]+=(1<<(j-1));
            }
        }
        for(int i=1;i<=k;i++){
            if(!(cur[1]&state[i])){
                dp[1][i]=1;
            }
        }
        for(int i=2;i<=n;i++){
            for(int j=1;j<=k;j++){
                if(cur[i]&state[j]) continue; ///枚举第i行的可行状态state[j]
                for(int t = 1;t<=k;t++){
                    if(cur[i-1]&state[t]) continue; ///枚举第i-1行的可行状态state[t]
                    if(state[j]&state[t]) continue; ///判断相邻两行状态是否合法
                    dp[i][j] = (dp[i][j]+dp[i-1][t]+mod)%mod;
                }
            }
        }
        int ans = 0;
        for(int i=1;i<=k;i++){
            ans = (ans+dp[n][i]+mod)%mod;
        }
        printf("%d
",ans);
    }
    return 0;
}