2012年第四届华为编程大赛决赛试题
决赛题目大概是这样：
在一个21x21的棋盘上，利用各种俄罗斯方块的图案，尽可能地填满全部棋盘。他在初始会给你额外放一个图案作为障碍，表示这个图案所在的地方已经被填上了
我一开始以为搜索就行了，但是搜索空间实在太大了，自己也想不出什么好的启发式或者剪枝算法
最后我的想法是，把大部分空间都用长条填充完，最后剩一个很小的区间再遍历。但是这样无法保证最优性，不知道这道题的正确解法是什么？
题目详细要求可以看http://blog.thpiano.com/?p=579
[解决办法]
由于题目设定的障碍方块只有两种情况，而且这两种情况还可以通过旋转变成相同，所以只考虑其中一种情况即可。以横向放置的为例。
首先考虑原始放置的障碍物不在棋盘最左上角和最右下角时。此时不论障碍块在什么地方，总能通过增加两个L型方块使之变成一个大小为4*3或者3*4的更大障碍块。接下来要做的就是用长条填充剩下的全部空间，最后刚刚有一个小方块不能被填充到。
原始障碍块在最左上角时如下填充左上角：
0 1 1 c c
1 1 d d c
d d d d c
d d c d d
c c c d d
这时在这右边是一个5*16空白，剩余的是一个16*21空白，这两个空白区域刚刚可以用长条填充完成。最后原始障碍块在最右下和最左上的情况是对称的。
[解决办法]
我认为这个可以剪枝的，可以简单证明，障碍图如果加上其他积木可以拼成矩形，那么就可以填满整个空间
这里有个限制条件就是21*21，如果可以无限大，几乎一定可以拼成一个矩形
所以出发点在于障碍图，在障碍图位置条件下，往外凑矩形
因此不要先着手解题，而是算出所有积木及其变换拼凑成最小矩形的算法
然后按照障碍图位置算其他积木填满21*21空间
