题目：http://poj.org/problem?id=3254
利用二进制压缩状态，每一个整数代表一行的01情况；
注意预处理出二进制表示下没有两个1相邻的数的方法，我的方法(不知为何)错了，看到了别人的优美方法；
再进行DP即可。
代码如下：
#include<iostream>
#include<cstdio>
using namespace std;
int m,n,a[15],num[15],p[3005],f[15][3005],tot,INF=100000000,ans;
//int pw(int w)
//{
// int ret=1;
// int sum=1;
// while(w)
// {
// ret*=2;
// if(w&1)sum*=ret;
// w/=2;
// }
// return sum;
//}
//void ap(int w,int b,int jl)//2^w b=0/1 +jl
//{
// if(w==n-1)
// {
// if(!b)p[++tot]=jl;
// else
// {
// p[++tot]=jl;
// p[++tot]=jl+pw(w);
// }
// return;
// }
// if(!b)ap(w+1,1,jl);
// else
// {
// ap(w+1,0,jl+pw(w));
// ap(w+1,1,jl);
// }
//}
inline bool ok(int x){ //判断状态x是否可行
if(x&x<<1) return false;//若存在相邻两个格子都为1，则该状态不可行
return true;
}
void init(){ //遍历所有可能的状态
int total = 1 << n; //遍历状态的上界
for(int i = 0; i < total; ++i){
if(ok(i))p[++tot] = i;
}
}
int main()
{
scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
{
scanf("%d",&a[j]);
num[i]*=2;
num[i]+=a[j];
}
init();
// ap(0,1,0);
// cout<<tot<<endl;
for(int i=1;i<=tot;i++)
{
// cout<<p[i]<<endl;
if(!(p[i]&(~num[1])))f[1][i]++;
}
for(int i=2;i<=m;i++)
{
for(int j=1;j<=tot;j++)
{
if(p[j]&(~num[i-1]))continue;
for(int k=1;k<=tot;k++)
{
if((p[k]&(~num[i]))||(p[k]&p[j]))continue;
f[i][k]+=f[i-1][j];
f[i][k]%=INF;
}
}
}
for(int i=1;i<=tot;i++)
{
ans+=f[m][i];
ans%=INF;
}
printf("%d",ans);
return 0;
}