巧铺地板
转自:http://tieba.baidu.com/f?kz=369526531#Scene_1我觉得这个题目做擂台赛不错，计算复杂度比较适合计算机解决:
长宽为2和1的瓷砖铺长宽为8和5的地板.
要求：
·把地板铺满.
·瓷砖不重叠.
·每个瓷砖可以横铺也可以竖铺
显然，一共需要20块瓷砖，方案数非常多.
问题1：20块瓷砖铺好地板的总方案是多少种？
问题2：若事先把k块瓷砖铺好，使得剩下的地方就只有唯一一种铺法了,请问k的最小值是多少？
砖１：
■■
砖２：
■
■
地板：
□□□□□□□□
□□□□□□□□
□□□□□□□□
□□□□□□□□
□□□□□□□□ 这个可能手数更方便
问题1：考虑清某一列的情况，再乘应该就可以了
□
□
□
□
□
向两边伸出，必伸出奇数个，不算左右上下对称，伸出一个的只有
□□ □
□ □
□ □□
□ □
□ □
这两种，伸出3个的多一些（也不太多），5个的只有32/2/2=8种
应该不是难题
问题2：沾极值感觉就比较复杂了，需要想一下 问题一就是问8X5方阵铺2X1的块，总共多少方案
估计数值很大
按块数分类吧 数目应该不大，先算有长方的（应该可以推出通项公式），然后再按我上面的方法数互相咬合的。
我数了一下，一列，并且向旁边伸出3个块好像只有12种，其中3个块在同侧的3种
□□ □□ □
□□ □□ □□
□□ □ □□
□ □ □
□ □□ □□
加上伸出1个块的，一面平齐的情况只有5种，一个个去推，肯定可以求出。
5*n矩阵的应该都可以求，但对于n*m的矩阵，还不知道如何搞 计算机求解也不会困难吧.dancing links. 第一问应该不难，甚至用dancing links也应该可以解决，但是有更好的方法。
第二问感觉上应该能够用计算机解决，但是我没有完全的把握，这个依赖于实际上k有多大 dancing links是什么?如何解？
对n*m的我又想了一下，如果将每个小竖条向上连，小横条向左连，好像等价于2分图的支撑森林，大家想想是不，如果真是就可以用caylay定理什么的了。
第二问，感觉应该先研究什么样的图可被覆盖，如果一个可覆盖的图加上一个圈，则覆盖方案不唯一 dancing links其实还是遍历，只是遍历过程中对链表的访问使用了些技巧，使得速度可以快一些，但是没有时间复杂度上的改善。 不是支撑树，是一些2叉树，感觉把长方形割成一个个杨表类似的东西，需要回家查查书了 计算了一下，8*5总共才14824种铺地方案，太少了，加大到16*5如何？