DP
注意虽然数据小但是搜索还是会超时
不能搜索
考虑DP：
但如果强行DP还是不够
那考虑优化:
每个格子只有两种状态：
选 or 不选 （当然如果这个格子是"贫瘠的"就一定不能选）
明显可以用一个2进制表示
而整行的状态就可以用一串2进制表示
状态的压缩就完成了
可能有人会疑惑n,m最大为12 , 2^12=4096 ，不会超时吗？
要注意虽然有4096种状态，但是真正有用到的状态只有不到500种
（显然 有用的状态就是 如果这一个状态2进制下这位为1，那么它上一位和下一位必定不能为1）
那就好了，用一个num数组存一下有用的状态就可以了
至于判断相邻两行的状态是否冲突也很简单：
if（num[ j ] & num[ k ]） 那么就冲突
转移方程：
设f[ i ][ j ]表示第 i 行的第 j 种状态有多少种方案：
则显然
f[ i ][ j ]+=f[ i-1 ][ k ] （状态j 与 状态 k 不冲突 且j和k都不与地图冲突）
那么最后的答案就是f[ n ][ i ]的和 (0<=i<=有用的状态总数)
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<cstring> using namespace std; const int mo=100000000; int n,m,a[15],b[15]; //b[i]是存第i行地图的状态（同样把状态压缩） int f[15][500],num[500],cnt;//f和num如上，cnt存有用的状态总数 inline void out(int now) { for(int i=m;i>=0;i--) if(now&(1<<i)) cout<<1; else cout<<0; cout<<endl; }//输出一个数的二进制表示，有助于调试 int main() { int res; cin>>n>>m; register int i,j;//用register int 会快一些 for(i=1;i<=n;i++) { res=0; for(j=1;j<=m;j++) scanf("%d",&a[j]);//读入单行的状态 for(j=0;j<m;j++) res+=((!a[m-j])<<j);//然后存在b中 b[i]=res; } for(i=0;i<(1<<m);i++) { if(i&(i<<1)) continue;//判断此状态是否有用 num[++cnt]=i; } f[0][1]=1;//初始化，第一种状态为什么也不放 for(i=1;i<=n;i++) for(j=1;j<=cnt;j++)//枚举有用的状态 { if(num[j]&b[i]) continue; for(int k=1;k<=cnt;k++)//同样枚举 { if((num[j]&num[k])||(num[k]&b[i-1])) continue;//判断冲突 f[i][j]=(f[i][j]+f[i-1][k])%mo;//更新 //cout<<f[i][j]<<" "<<i<<" "<<j<<" "<<k<<endl; //out(num[k]); } //cout<<endl; } int ans=0; for(i=1;i<=cnt;i++) ans=(ans+f[n][i])%mo; cout<<ans;//输出 return 0; }