把第i行状态分成两类,一类是没有打横的,一类是有打横的,没有打横的根据i-1来进行dp,有打横的根据当前行来进行dp

#include <stdio.h>
#include <cstring>

#define MAXN 11

int h, w;
__int64 dp1[MAXN][1<<MAXN], dp2[MAXN][1<<MAXN][MAXN], ans;
bool flag;

bool inSt(int i, int s){
	return ((1<<i)&s)>0;
}

int main(){
	int S, i, j, k, s, now;
	while (1){
		scanf("%d%d",&h,&w);
		if (h==0&&w==0) break;
		S=(1<<w)-1;
		memset(dp1,0,sizeof(dp1));
		memset(dp2,0,sizeof(dp2));
		dp1[0][0]=1;
		for (i=0;i<h;i++){
			for (s=0;s<=S;s++){
				if (i>0){
					now=S;
					for (j=0;j<w;j++)
						if (inSt(j,s)) now-=(1<<j);
					dp1[i][s]+=dp1[i-1][now];
					for (j=0;j<w;j++)
						dp1[i][s]+=dp2[i-1][now][j];
				}
				for (j=0;j<w-1;j++){
					if (inSt(j,s)&&inSt(j+1,s)){
						now=s-(1<<j)-(1<<(j+1));
						dp2[i][s][j]+=dp1[i][now];
						for (k=0;k<j-1;k++){
							dp2[i][s][j]+=dp2[i][now][k];
						}
					}
				}
			}
		}
		ans=dp1[h-1][S];
		for (i=0;i<w;i++)
			ans+=dp2[h-1][S][i];
		printf("%I64d\n",ans);
	}
	return 0;
}