【题解】
首先将棋盘转化成"竖长形"(m<=n)，然后从上往下逐行推进、每行从左往右枚举放骨牌的格子(规定骨牌只能往上、左两个方向放，不会影响到尚未枚举的格子)
那么正枚举的当前行可能是参差不齐的，在当前行产生轮廓(用1/0表示当前是否被覆盖，若当前格选择填0，其上方相邻位必为1，否则再无法被覆盖)以枚举格的坐标和当前行的"轮廓"为状态，，即：d[cur][k]：棋盘第cur个格在状态为k时的方案数其中，棋盘格位置(i,j)用cur来代替(相当于d[i][j][k]，而d[i][j][k]只与(i,j-1)有关，因此采用滚动数组) k是一个m位的二进制数，利用状压来表示(i,j-1),(i,j-2),…,(i,1),(i-1,m),(i-1,m-1),…,(i-1,j)是否被覆盖，这确定了一个封闭轮廓，记为"Km,…K2,K1"(i,j)有三种决策：不放骨牌：(i-1,j)必须有骨牌(Km==1)，状态：1,…,K2,K1 (对(i,j)来说) -> K(m-1)…K2,K1,0 (对(i,j+1)或j==m时(i+1,1)来说)放朝上的骨牌：(i-1,j)必须无骨牌(i!=1&&Km==0)，状态：0,K(m-1),…,K2,K1 -> K(m-1)…K2,K1,1
放朝左的骨牌：(i-1,j)必须有骨牌，(i,j-1)必须无骨牌(j!=1&&Km==1&&K1==0)，状态：1,K(m-1),…,K2,0 -> K(m-1)…K2,1,1
【代码】
#include<stdio.h>#include<stdlib.h>#include<string.h>long long d[2][4000]={0};void jh(int* a,int* b){int t=*a;*a=*b;*b=t;}int main(){int n,m,i,j,k,cur;while(scanf("%d%d",&n,&m)==2&&n!=0){if(n<m) jh(&n,&m);cur=0;d[0][(1<<m)-1]=1;/*为什么其他的d[0][k]不用赋0：若k的二进制位Ki为0，则d[0][k]只对(1,Ki)上放朝上的骨牌起作用，但第一行不能选择"放朝上的骨牌"，因此d[1]["Ki朝上放骨牌对应的状态"]并未被改变，还是0，当然也不会影响接下来的几行*/for(i=1;i<=n;i++)for(j=1;j<=m;j++){cur^=1;memset(d[cur],0,sizeof(d[cur]));for(k=0;k<(1<<m);k++){if( k&(1<<m-1) ) d[cur][(k<<1)^(1<<m)]+=d[1-cur][k];//不放骨牌if( i!=1 && (k&(1<<m-1))==0 ) d[cur][(k<<1)+1]+=d[1-cur][k];//放朝上的骨牌if( j!=1 && (k&(1<<m-1)) && (k&1)==0 ) d[cur][(k<<1)^(1<<m)+3]+=d[1-cur][k];//放朝左的骨牌}}printf("%lld\n",d[cur][(1<<m)-1]);}return 0;}
爱情不是避难所，想进去避难的话，是会被赶出来的。
