一本通 1593

农场主 John 新买了一块长方形的新牧场，m*n (1≤M≤12;1≤N≤12)，John 打算在牧场上的某几格里种上美味的草 。

遗憾的是，有些土地相当贫瘠，不能用来种草。并且，John 不会选择两块相邻的土地，也就是说，没有哪两块草地有公共边。

如果不考虑草地的总块数，那么，一共有多少种种植方案可供他选择？

#include <bits/stdc++.h>
using namespace std ;
 const int mod=1e8,N=15,M=4300;
 
 int tot,n,m,f[N][M],a[N][N],g[N];
 bool b[M];
 
 signed main(){
      int i,j,k;
      cin>>n>>m;
      for(i=1;i<=n;i++)
       for(j=1;j<=m;j++) cin>>a[i][j];
      
      for(i=1;i<=n;i++)
       for(j=1;j<=m;j++)
        g[i]=(g[i]<<1)+a[i][j];
        
     tot=1<<m;
      for(i=0;i<tot;i++) 
      b[i]=((i&(i<<1))==0&&(i&(i>>1))==0);
     f[0][0]=1;
      
      for(i=1;i<=n;i++)
       for(j=0;j<tot;j++)
        if(b[j]&&(j&g[i])==j)
         for(k=0;k<tot;k++){
             if((k&j)==0) f[i][j]+=f[i-1][k];
         }
         
      for(j=i=0;i<tot;i++) j+=f[n][i],j%=mod;
      
      cout<<j;
 }