PKU 3254 Corn Fields
http://poj.org/problem?id=3254
n*mのフィールドがある。
このフィールドにコーンを育てたい。
この時、フィールドは豊かな土地とそうでない土地があり、豊かでない土地ではコーンを育てることができない。
また、このフィールドのコーンがいるところでは牛を飼うが、上下左右の隣り合うフィールドには牛がいないようにしたい。
コーンの植え方が何通りあるかを答えろというような問題。
bitDP。
int dp[12][1<<12]; int fe[12]; int MOD=100000000; int m,n; void dfs(int row,int ne,int st,int fo,int add){ if(ne==n){ dp[row][st]=(dp[row][st]+add)%MOD; return; } dfs(row,ne+1,st,fo,add); if(!(fo&(1<<ne)))dfs(row,ne+1,st|1<<ne,fo|1<<ne+1,add); } main(){ cin>>m>>n; rep(i,m){ rep(j,n){ int t; cin>>t; fe[i]|=(!t)<<j; } } dfs(0,0,0,fe[0],1); for(int i=1;i<m;++i){ rep(j,(1<<n))dfs(i,0,0,fe[i]|j,dp[i-1][j]); } int ans=0; rep(i,(1<<n))ans=(ans+dp[m-1][i])%MOD; cout<<ans<<endl; }