Poj 3254 Corn Fields (DP_状态压缩DP)

题目大意：给定一个n*m的矩阵，矩阵上有数值有0和1，1表示这个坐标可以放置东西，要求放置的东西不能相邻，问有多少种放法？n,m<=12
解题思路：简单状态DP，dp[i][j]表示第i行放置东西的状态为j的方法数，j是一个若干个二进制数的和，表示哪些列放置了东西。
                  然后进行递推，dp[i][j]  =  sum(dp[i-1][k]) (k状态和j状态不冲突)
测试数据：
 2 3
1 1 1
0 1 0

代码：
[cpp] 
#include <stdio.h> 
#include <string.h> 
#define MIN 15 
#define MAX (1<<13) 
#define MOD 100000000 
 
 
int dp[MIN][MAX],n,m; 
int ans,map[MIN][MIN],state[MIN]; 
 
 
int CheckAdj(int st) { 
 
    return !(st & (st>>1)); 
} 
int CheckPre(int cur,int pre) { 
 
    return !(cur & pre); 
} 
void State_Dp() { 
 
    int i,j,k,st = (1<<m); 
 
    //初始化 
    for (i = 0; i < st; ++i) 
        if (i == (i & state[0]) && CheckAdj(i)) 
            dp[0][i] = 1;//printf("0 %d %d/n",i,dp[0][i]); 
 
 
    //状态转移 dp[i][j] = sum(dp[i-1][k]) (!(j&k)即j状态和k状态不冲突) 
    for (i = 1; i < n; ++i) 
        for (j = 0; j < st; ++j) 
            if (j == (j & state[i]) && CheckAdj(j)) { 
 
                int sum = 0; 
                for (k = 0; k < st; ++k) 
                    if (CheckPre(j,k)) sum = (sum + dp[i-1][k]) % MOD; 
                dp[i][j] = sum;//printf("i=%d j=%d %d/n",i,j,dp[i][j]); 
            } 
} 
 
 
int main() 
{ 
    int i,j,k; 
 
 
    scanf("%d%d",&n,&m); 
    for (i = 0; i < n; ++i) 
        for (j = 0; j < m; ++j) { 
 
            scanf("%d",&map[i][j]); 
            if (map[i][j] == 1) 
                state[i] |= (1<<j); 
        } 
 
 
    State_Dp(); 
    for (ans = i = 0; i < (1<<m); ++i) 
        ans = (ans + dp[n-1][i]) % MOD; 
    printf("%d/n",ans); 
} 

作者：woshi250hua