思路

$f[i,j]$，$i$表示行，$j$表示状态，状态中的$0$表示这一行的木块在下一行不凸出，$1$表示在下一行凸出。那么当从当前枚举状态时需满足：当前行的状态和上一行的状态同一个列位置不能有两个凸出，以及当前行的横放木块要合理，也就是对于上一行不凸出的列位置和当前行也不凸出的列位置放的一定是横着的木块，那么连续的横着的个数应该是偶数。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=12;
long long f[N][1<<N];// 1表示在下一行有凸出，0表示在下一行没有凸出
int n,m;
vector<int> v,vv[1<<N];
bool check(int x){
    x|=(1<<m);  //相当于在最后放一个竖着的挡板，防止横着的木块越界
    for(int i=0;i<m;++i){
        if( !(x&(1<<i)) &&(x&(1<<(i+1))) ) return false;
        if( !(x&(1<<i)) &&!(x&(1<<(i+1))) ) i++;
    }
    return true;
}
int main(){
    int T;
    for(int i=0;i<(1<<N);++i){
        v.push_back(i);
        vv[i].clear();
    }
    for(int i=0;i<v.size();++i){
        int x=v[i];
        for(int j=0;j<v.size();++j){
            int y=v[j];
            if( !(x&y) ){
                vv[i].push_back(y);
            }
        }
    }
    while(cin>>n>>m){
        if(n==0&&m==0) break;
        f[0][0]=1;
        for(int i=1;i<=n;++i){
            for(int j=0;j<v.size();++j){
                int x=v[j];
                if(x>=(1<<m)) break;
                f[i][x]=0;
                for(int k=0;k<vv[j].size();++k){
                    int y=vv[j][k];
                    if(y>=(1<<m)) break;
                    if(!check(x|y)) continue;
                    f[i][x]+=f[i-1][y];
                }
            }
        }
        cout<<f[n][0]<<endl;

    }
    return 0;
}