POJ 3254 Corn Fields（状态压缩）

一道状态压缩的题,错了好多次....应该先把满足的情况预处理出来

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int fitnum,n,m;

int maps[],state[<<];

int dp[][<<];

#define mod 1000000000

int main()

{

    while(~scanf("%d%d",&n,&m))

    {

        memset(maps,,sizeof(maps));

        fitnum = ;

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

        {

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

            {

                int s;

                scanf("%d",&s);

                if(!s)

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

            }

        }

        memset(dp,,sizeof(dp));

        memset(state,,sizeof(state));

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

        {

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

            state[fitnum++] = i;

        }

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

        {

            if(!(state[i] & maps[]))

                dp[][i] = ;

        }

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

        {

            for(int k = ;k < fitnum;k++)

            {

                if(state[k] & maps[i]) continue;

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

                {

                    if(state[j] & maps[i-]) continue;

                    if(state[j] & state[k]) continue;

                    dp[i][k] = (dp[i][k]%mod + dp[i-][j]%mod)%mod;

                }

            }

        }

        int ans = ;

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

        {

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

        }

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

    }

    return ;

}