f[i][j]表示前i-1列已经摆好，并且第i列的状态是j的所有合法方案数

先预处理，再dp

#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 12,M = 1 << N;
int n,m;
long long f[N][M];
bool st[M];

int main()
{
    while(cin>>n>>m,n || m)
    {
       memset(f,0,sizeof f);
       //下面首先是预处理所有的状态，判断每个状态是否有连续个奇数的0
       for(int i = 0;i< 1<<n;i++)
       {
           int cnt = 0;
           st[i] = true;
           for(int j = 0;j<n;j++)
           {
               if((i>>j) & 1)//如果碰到1了
               {
                   if(cnt & 1)
                   {
                        st[i] = false;//判断前面是否有奇数个0
                        break;
                   }
                   cnt = 0;
               }
               else cnt++;//碰到0就+1
           }
           if(cnt & 1)st[i] = false;
       }
       //dp过程
       f[0][0] = 1;
       for(int i = 1;i<=m;i++)
        for(int j = 0;j< 1<<n ;j++)
            for(int k = 0;k< (1<<n);k++)//枚举上一位的所有状态
                if((j & k)==0 && st[j|k])//如果满足条件没有冲突并且没有奇数个0
                    f[i][j] += f[i-1][k];//那么就加上上一位的方案数

        cout<<f[m][0]<<endl;
    }
}