用一个vector容器来记录当前状态下有哪些状态可以继承。
比如说vec[i]里面的所有的数代表当第一行为i状态时，第二行的可行状态。
对于状态i，其二进制中0的地方表示为当前状态为竖着的木板的下半部分。
其二进制中1的地方表示为当前状态为横着的木板或者竖着的木板的上半部分。
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define ll __int64
int n,m;
ll dp[15][5001];
vector<int>vec[5001];
void init()
{if(n<m)swap(n,m);memset(dp,0,sizeof(dp));;dp[1][(1<<m)-1]=1;for(int i=0;i<(1<<m);i++)vec[i].clear();
}
void dfs(int a,int x,int y,int m)
{if(a>=m){if(x<(1<<m)&&y<(1<<m)){vec[x].push_back(y);}return ;}dfs(a+1,(x<<1)|1 , y<<1 ,m);dfs(a+1, x<<1 ,(y<<1)|1 ,m);dfs(a+2,(x<<2)|3 ,(y<<2)|3 ,m);
}
void chu()
{dfs(0,0,0,m);int i,j,k;for(i=1;i<=n;i++){for(j=0;j<(1<<m);j++){for(k=0;k<vec[j].size();k++){dp[i+1][vec[j][k]]+=dp[i][j];}}}cout<<dp[n+1][(1<<m)-1]<<endl;
}
int main()
{while(~scanf("%d %d",&n,&m)&&(n||m)){init();chu();}return 0;
}