http://poj.org/problem?id=2411
下次还是去学习下dfs的写法吧 自己乱写的好像有点乱 乱七八糟改了一通过了
以1 1 表示横着的 1 0 表示竖着的 枚举每一行的状态 再枚举前一行的状态判断是否可以同存
注意最后一行要特殊判断一下 0夹着着的1必须为偶数
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
using namespace std;
#define N 3010
#define LL __int64
LL dp[][N],o[][N],k[];
int main()
{
int i,j,n,m,e,g;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n==&&m==)
break;
memset(dp,,sizeof(dp));
memset(k,,sizeof(k));
memset(o,,sizeof(o));
if(n%!=&&m%!=)
{
printf("0\n");
continue;
}
o[][] = (<<m)-;
dp[][o[][]] = ;
k[] = ;
for(i = ; i <= n ; i++)
{
for(j = ; j < <<m ; j++)
{
for(g = ; g <= k[i-] ; g++)
{
LL gg = o[(i+)%][g];
int kk = ;
for(e = ; e < m ; e++)
{
if((j&(<<e))==&&(gg&(<<e))==)
break;
if((j&(<<e))!=&&(gg&(<<e))!=)
kk++;
else
if(kk%!=) break;
else kk=;
}
if(kk%==&&e==m)
dp[i][j]+=dp[i-][gg];
}
if(dp[i][j])
{
k[i]++;
o[(i+)%][k[i]] = j;
}
}
}
LL ans=;
for(i = ; i < <<m ; i++)
{
if(dp[n][i]==)
continue;
int kk=;
for(e = ; e < m ; e++)
{
if((i&(<<e))==&&(kk%)!=)
break;
if((i&(<<e))==&&(kk%)==)
kk = ;
if((i&(<<e))!=)
kk++;
}
if(kk%==&&e==m)
ans+=dp[n][i];
}
printf("%I64d\n",ans);
}
return ;
}