动态规划题。思路就是暴力搜索，以每层为单位搜索，并且状态数目不多，把每一行的方格压缩为二进制编码。
Python代码：
# -*- coding: utf-8 -*-
import sys
H = W = 0
# 保存状态转化的结果
tran = []
def dfs(n, _from, to):
'''计算出宽度为W的时候，上下两层不同的方案数
_from表示上层的状态，to表示下层的状态
_from中1表示填充，0表示未填充
to中1表示填充（或者说第二层必须想办法填充）
0表示未填充（或者说第二层不需要填充或不能填充，因为上一层已经用竖块填充了）
'''
global W, tran
if n > W:
return
if n == W:
tran.append((_from, to))
return
# 水平放置砖块
dfs(n 2, (_from << 2) 3, (to << 2) 3)
# 竖直放置砖块
dfs(n 1, (_from << 1) 1, to << 1)
# 不放置砖块
dfs(n 1, _from << 1, (to << 1) 1)
def dp():
global W, H, tran
# 保存各层的递推结果
# b[i][j]表示0到i - 1行全填满且第i行状态为j的所有可能数目
# 迭代求出b[H][(1 << W) - 1]即为答案
b = [[0 for j in xrange(2048)] for i in xrange(12)]
# 假设存在第0层，且全部填充1，只有一种情况
b[0][(1 << W) - 1] = 1
for i in xrange(H):
for j in tran:
b[i 1][j[1]] = b[i][j[0]]
print b[H][(1 << W) - 1]
def main():
global W, H, tran
for line in sys.stdin:
H, W = [int(a) for a in line.split()]
if H == W == 0:
break
tran = []
if H < W:
H, W = W, H
dfs(0, 0, 0)
dp()
if __name__ == '__main__':
main()
