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 MOD100000000using namespace std;const int maxn=15;int isFertile;int f;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==0||(s&(1<<(k+1))))) break; } if(k>=m) { a=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!=-1) return f%MOD; int q,head=0,tail=0; int s1=~s; s1=s1&((1<<m)-1); for(int k=0;k<m;k++) { if(!isFertile)s1=s1^(1<<k); } dfs(s1,0,q,tail,row); f=0; if(row==n-1) return f=tail%MOD; for(head=0;head<tail;head++) { f=(f+dp(row+1,q))%MOD; } return f;}int main(){ cin>>n>>m; for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin>>isFertile; memset(f,-1,sizeof(f)); int q,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||(s&(1<<(k+1))))) break; } if(k>=m) {q=s;} } if(n==1) {cout<<tail<<endl;return 0;} int sum=0; for(head=0;head<tail;head++) sum=(sum+dp(1,q))%MOD; cout<<sum<<endl; return 0;}
页:
[1]