将方格的摆放分成两种：
1.水平摆放：此时所占的两个格子都记为1。
2.竖直摆放：此时底下那个格子记为1，上面那个记为0。
这样的话，每行都会有一个状态表示。
定义：dp[i][s]表示考虑已经填到第i行，这一行状态为s的方法数
转移：dp[i][s] = dp[i][s]+dp[i-1][s'] (s'为上一行的状态，当第i行和第i-1行能够满足条件时，进行转移)
先预处理出所有满足条件的第一行，然后从第二行开始转移。
最后答案为dp[n][(1<<m)-1].
当n<m时交换n和m可减小1<<m，即减少状态数。
代码：
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #define Mod 1000000007 #define ll long long using namespace std; #define N 2100 ll dp[13][N]; int n,m; int FirstLine(int state) { int i=0; while(i<m) { if(state & (1<<i)) //第i列为1,第i+1列也存在且必须为1 { if(i < m-1) { if(state & (1<<(i+1))) //第i+1列为1 i += 2; else return 0; } else return 0; } else i++; } return 1; } int Can(int ka,int kb) //ka:这一行，kb:上一行 { int i = 0; while(i<m) { if(ka & (1<<i)) //这一行i列为1 { if(kb & (1<<i)) //如果上一行i列为1，则为两个水平块 { if(i < m-1 && (ka & (1<<(i+1))) && (kb & (1<<(i+1)))) i += 2; else return 0; } else //上一行为0,竖着放的 i++; } else //这一行i列为0,上一行i列必须填充 { if(kb & (1<<i)) i++; else return 0; } } return 1; } int main() { int i,j,sa; int state1,state2; while(scanf("%d%d",&n,&m)!=EOF) { if((n*m)%2) { puts("0"); continue; } memset(dp,0,sizeof(dp)); if(n < m) swap(n,m); int MAX = (1<<m)-1; for(sa=0;sa<=MAX;sa++) { if(FirstLine(sa)) //此状态可以作为第一行的状态 dp[0][sa] = 1; } for(i=1;i<n;i++) //行递增 { for(state1=0;state1<=MAX;state1++) { for(state2=0;state2<=MAX;state2++) { if(Can(state1,state2)) dp[i][state1] += dp[i-1][state2]; } } } printf("%lld ",dp[n-1][MAX]); } return 0; }