状态压缩的dp,强大的discuss.

如果是横着的就定义11，如果竖着的定义为竖着的01，这样按行dp只需要考虑两件事儿，当前行&上一行，是不是全为1，不是说明竖着有空（不可能出现竖着的00），另一个要检查当前行里有没有横放的，但为奇数的1 

	#include <cstdio>  
#include <cstring>  
int n,m;
int full;
long long dp[12][1<<11];

bool fit1(int j)
{
    int bits=0;
    while(j)
    {
        if(j&1) ++bits;
        else
        {
            if(bits&1) return 0;
            else bits=0;
        }
        j>>=1;
    }
    if(bits&1) return 0;
    return 1;
}
bool fit2(int j,int k)
{
    if((j|k)!=full) return 0;
    return fit1(j&k);
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int i,j,k;
    while(scanf("%d%d",&n,&m),n)
    {
        if(n&m&1) {puts("0");continue;}
        full=(1<<m)-1;
        memset(dp,0,sizeof(dp));
        for(j=0;j<=full;j++)
            if(fit1(j))
                dp[1][j]=1;
        for(i=2;i<=n;i++)
        {
            for(j=0;j<=full;j++)
                for(k=0;k<=full;k++)
                    if(fit2(j,k)) dp[i][j]+=dp[i-1][k];
        }
        printf("%lld\n",dp[n][full]);
    }
}