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;
}