学步园

思路：状态压缩DP dp[i][j] 表示第i行，第sj状态下的方法个数，可得出状态方程 dp[i][j] =
sigma(dp[i-1][k]);

//168K   
0MS
#include <stdio.h>
#include <string.h>
#define M 15
#define Max 200
const int mod = 100000000;

int dp[2][Max];
int a[M][M],s[Max],n,m; //s[i] 表示第i种状态 a[i][0]存储第i行哪某一列是否能种
1表不能种

void dfs (int p,int spc,int now,int
cnt)   //预处理算出每种状态
{
    if (p ==
m)
    {
       
s[++s[0]] = now;
       
return ;
    }
    dfs
(p+1,spc+1,now<<1,cnt);
    if (spc
>=
1)                  
//spc 表示每两个1的距离间
       
dfs (p+1,0,now<<1|1,cnt+1);
}
int main ()
{
    int
i,j,k,p;
    while
(~scanf ("%d%d",&n,&m))
    {
       
memset (a,0,sizeof(a));
       
for (i = 1; i <= n; i ++)
           
for (j = 1; j <= m; j ++) //求出每一行哪一列能种不能种
           
{
               
scanf ("%d",&a[i][j]);
               
a[i][j] = a[i][j]^1;
               
if (a[i][j] == 1)
                   
a[i][0] = a[i][0] + (1<<(m-j));
           
}
       
s[0] = 0;
       
dfs (0,1,0,0);
       
dp[0][1] =
1;              
//不种也算一种
       
for (i = 1; i <= n; i ++)
       
{
           
for (j = 1; j <= s[0]; j ++)