题目：Tromino 是一个由棋盘上的三个邻接方块组成的L型瓦片，我们的问题是，如何用tromino覆盖一个缺少了一个方块（可以在棋盘上的任何位置）的(2^n)*(2^N)棋盘。除了这个缺少的方块，tromino应该覆盖棋盘上的所有方块，而且不能重叠。
原题见《算法设计与分析基础》98页。
思想是使用分治法，即把大问题划分为几个小问题。8*8的化为4个4*4的，4*4的化为四个2*2的，当化为2*2的时候，解法就很简单了，直接把2*2矩阵中另外三个位置用L型瓦片覆盖就行了。当返回到上一层4*4矩阵的时候，把与刚才2*2矩阵相邻的三个位置用一块瓦片覆盖。因为瓦片占三个位置，恰好在剩下三个矩阵中每个占一个位置，然后又生成了另外三个2*2且每个都缺一个位置的问题。
简要代码如下：
Tromino(n,i,j){//n为矩阵是2的次方数，i和j为缺少的位置的坐标
int x,y;
if(n>1){
if(i<2^(n-1)-1)//求出缺少点在当前矩阵的四个子矩阵中的哪一个中
x=0;
else x=1;
if(j<2^(n-1)-1)
y=0;
else y=1;
Tromino(n-1,i-x*2^(n-1),j-y*2^(n-1));//转化为规模小一层的问题
L(a,b,c);//把三个位置用L型瓦片覆盖
Trimino(n-1,...);//解决产生的三个规模小一的问题
Trimino(n-1,...);
Trimino(n-1,...);
}
if(n==1)
L(...);//标好除去i,j位置外的三个位置
}
