题意：一个矩阵里有很多格子，每个格子有两种状态，可以放牧和不可以放牧，可以放牧用1表示，否则用0表示，在这块牧场放牛，要求两个相邻的方格不能同时放牛，即牛与牛不能相邻。问有多少种放牛方案(一头牛都不放也是一种方案)
思路：dp[i][s] 代表第i行状态为s（s是每个位置放与不放组成的0-1序列对应的十进制数）时所能得到的方案总数
递推方程：dp[i][s] = Σdp[i-1][f] (f为i-1行的状态)
判断状态合法的方案是，s中不能有相邻的1，s中的1必须满足题目给定矩阵，即矩阵有1的地方s可以放1，s与f不能在同一位置有1。
初始化：dp[1][s] = 0或1（代表第一行状态为s是否合法）
#include<cstring>
#include<cstdio>
#define mod 1000000000
int stk[400],top,N,M,a[15][15],dp[15][400];
inline bool checkline(int i,int x)
{
for(int j=0,pre=0;j<M;++j,pre=x&1,x/=2)
if(x&1 && !a[i][j+1]) return 0;
return 1;
}
inline bool checkline(int x)
{
for(int j=0,pre=0;j<M;++j,pre=x&1,x/=2)
if(x&1 && pre) return 0;
return 1;
}
void init()
{
memset(dp,0,sizeof(dp));
top=0;
for(int s=0;s< (1<<M) ;++s)
if(checkline(s)) stk[top++]=s;
}
int main()
{
while(~scanf("%d%d",&N,&M))
{
for(int i=1;i<=N;++i)
for(int j=1;j<=M;++j) scanf("%d",&a[i][j]);
init();
for(int j=0;j<top;++j) dp[1][j]=checkline(1,stk[j]);
for(int i=2;i<=N;++i)
for(int j=0;j<top;++j)
{
if(!checkline(i,stk[j])) continue;
for(int k=0;k<top;++k)
{
if((stk[j]&stk[k]) || !checkline(i-1,stk[k])) continue;
dp[i][j] = (dp[i][j]%mod+dp[i-1][k]%mod)%mod;
}
}
int ans=0;
for(int j=0;j<top;++j)
ans = (ans%mod+ dp[N][j]%mod)%mod;
printf("%d\n",ans);
}
return 0;
}