状态压缩 poj 3254

n * m 个玉米

n*m个数字 0 或者1

1可以种玉米 0 不能  种玉米不能相邻

计算有几种 种的方法

#include<stdio.h>

#include<algorithm>

#include<string.h>

using namespace std;

#define MAXN 13

#define MAXN1 10000

#define mod 100000000

int n,m;

int z[MAXN][MAXN];

int num[MAXN1];

int cnt;

int dp[MAXN][MAXN1];  //dp[i][j]   第一维是行 第二维是列 表示这一行这个状态的数目

int x[MAXN]; //用来记录每一行的二进制数   1

void solve()                // 0&1 =0   就1&1=1

{

    for(int i=;i<(<<m);i++)   //所有可能的状态  就是这一行不可能相邻  10010  100100  这样可以  11010  110100  不行

        if((i&(i<<))==)

            num[cnt++]=i;

}

bool jug(int state,int r)  //这个状态 和这一行是否矛盾

{

    if(!(state&(~x[r])))

        return ;

    return ;

}

int main()

{

    while(scanf("%d%d",&n,&m)!=EOF)

    {

            for(int i=;i<=n;i++)

                for(int j=;j<=m;j++)

                    scanf("%d",&z[i][j]);

            cnt=;

            solve();

            memset(dp,,sizeof(dp));

            memset(x,,sizeof(x));

            for(int i=;i<=n;i++)

            {

                for(int j=;j<=m;j++)

                    if(z[i][j])

                        x[i]+=(<<(m-j));

            }

            dp[][]=;

            for(int i=;i<=n;i++)

            {

                for(int st=;st<cnt;st++)

                {

                    if(jug(num[st],i)) //这一行 和 这个状态

                    {

                        for(int pa=;pa<cnt;pa++)

                        {

                            if(jug(num[pa],i-)&&!(num[st]&num[pa]))//前一行和前一个状态 这和状态和前一个状态

                                dp[i][num[st]]+=dp[i-][num[pa]];

                        }

                    }

                }

            }

            int ans=;

            for(int i=;i<cnt;i++)        //所有的数目要加一下

                ans=(ans+dp[n][num[i]])%mod;

            printf("%d\n",ans);

    }

    return ;

}