经典的状态压缩DP。f[i][j]表示第i行，方格排布为二进制数j（第k位上为1表示凸出一个格子，为0表示不凸出）的方案数。用DFS进行状态转移。
如果行数比较多的话，可以用矩阵乘法优化。因为每行的状态转移都是相同的。设烈数为m，行数为n，可以做到O(2
3mlogn)。
/**//*************************************************************************
Author: WHU_GCC
Created Time: 2007-8-28 20:53:12
File Name: pku2411.cpp
Description:
************************************************************************/
#include <iostream>
long long f[12][2048], n, m;
void dfs(int i, int j, int jj, int s)
{
if (s == m)
f[i + 1][jj] += f[i][j];
else if ((jj & (1 << s)) == 0)
{
dfs(i, j, jj | (1 << s), s + 1);
if (s < m - 1 && (jj & (1 << (s + 1))) == 0) dfs(i, j, jj, s + 2);
}
else
dfs(i, j, jj & ~(1 << s), s + 1);
}
int main()
{
while (scanf("%d%d", &n, &m), n + m != 0)
{
memset(f, 0, sizeof(f));
f[0][0] = 1;
for (int i = 0; i < n; i++)
for (int j = 0; j < (1 << m); j++)
if (f[i][j])
dfs(i, j, j, 0);
printf("%I64d\n", f[n][0]);
}
return 0;
}