POJ 3254 Corn Fields

格桑花

Corn Fields

题目来源：http://poj.org/problem?id=3254

题目大意：一个人买了一个N*M个方格组成的农场，有部分方格不能种植。现在需要种草给牛吃，而牛又不喜欢挨着吃（don’t share an edge–>两个方格无公共边），不种草也算一种方案，求种植方案数。


此题与Mondriaan's Dream 类似，就不多讲了。

#include <iostream>#include <memory.h>#define MOD  100000000using namespace std;const int maxn=15;int isFertile[maxn][maxn];int f[maxn][1<<maxn];int n,m;void dfs(int s,int p,int *a,int &tail,int row){    if(p==m)    {        int k;        for(k=0;k<m;k++)        {            if(s&(1<<k)&&(isFertile[row][k]==0||(s&(1<<(k+1)))))     break;        }        if(k>=m)        {            a[tail++]=s;        }        return ;    }    if((s&(1<<p))==0) {dfs(s,p+1,a,tail,row);}    else    {        dfs(s,p+1,a,tail,row);        dfs(s^(1<<p),p+1,a,tail,row);    }}int dp(int row,int s){    if(f[row]!=-1)   return f[row]%MOD;    int q[1<<maxn],head=0,tail=0;    int s1=~s;    s1=s1&((1<<m)-1);    for(int k=0;k<m;k++)    {        if(!isFertile[row][k])  s1=s1^(1<<k);    }    dfs(s1,0,q,tail,row);    f[row]=0;    if(row==n-1)    return f[row]=tail%MOD;    for(head=0;head<tail;head++)    {        f[row]=(f[row]+dp(row+1,q[head]))%MOD;    }    return f[row];}int main(){    cin>>n>>m;    for(int i=0;i<n;i++)    for(int j=0;j<m;j++)    cin>>isFertile[j];    memset(f,-1,sizeof(f));    int q[1<<maxn],head=0,tail=0;    for(int s=0;s<(1<<m);s++)    {//枚举第一行的所有合法状态        int k;        for(k=0;k<m;k++)        {            if(s&(1<<k)&&(isFertile[0][k]==0||(s&(1<<(k+1)))))     break;        }        if(k>=m)    {q[tail++]=s;}    }    if(n==1)    {cout<<tail<<endl;return 0;}    int sum=0;    for(head=0;head<tail;head++)    sum=(sum+dp(1,q[head]))%MOD;    cout<<sum<<endl;    return 0;}