經(jīng)典的狀態(tài)壓縮DP。f[i][j]表示第i行，方格排布為二進(jìn)制數(shù)j（第k位上為1表示凸出一個(gè)格子，為0表示不凸出）的方案數(shù)。用DFS進(jìn)行狀態(tài)轉(zhuǎn)移。
如果行數(shù)比較多的話，可以用矩陣乘法優(yōu)化。因?yàn)槊啃械臓顟B(tài)轉(zhuǎn)移都是相同的。設(shè)烈數(shù)為m，行數(shù)為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;
}