分治算法之 棋盘覆盖问题（完整代码实现）
我在这里是用了一个简化的方式，只是代码简化，还是分治递归思想。一分为4，直至2*2时可直接解决。
四种骨牌的摆放刚好对应：dir[4][2] = { { 0, 0 }, { 0, 1 }, { 1, 1 }, { 1, 0 } }; 这四个方向。
而这4个方向，又可用来判断残缺位置的 4个方向（左上，右上，右下，左下）。
因此可以用循环，而不是依次判断四个方向，简化代码。
也可以用一个全局变量title 表示第几个骨牌，然后输出的时候可以用一个title代替ABCD.
copy:
【解题思路】：将2^k x 2^k的棋盘，先分成相等的四块子棋盘，其中特殊方格位于四个中的一个，构造剩下没特殊方格三个子棋盘，将他们中的也假一个方格设为特殊方格。如果是：
左上的子棋盘（若不存在特殊方格）----则将该子棋盘右下角的那个方格假设为特殊方格
右上的子棋盘（若不存在特殊方格）----则将该子棋盘左下角的那个方格假设为特殊方格
左下的子棋盘（若不存在特殊方格）----则将该子棋盘右上角的那个方格假设为特殊方格
右下的子棋盘（若不存在特殊方格）----则将该子棋盘左上角的那个方格假设为特殊方格
当然上面四种，只可能且必定只有三个成立，那三个假设的特殊方格刚好构成一个L型骨架，我们可以给它们作上相同的标记。这样四个子棋盘就分别都和原来的大棋盘类似，我们就可以用递归算法解决。
欢迎使用棋盘覆盖程序：分别A,B,C,D代表4种不同方向的骨牌: A B CC DDAA BB C D输入3个数，分别为棋盘大小N(小于1000)，残缺位置X,Y(1到N之间):4 2 3CCDDCB DBBBABBAA
这是书上的代码（不全）：
void ChessBoard(int tr, int tc, int dr,int dc, int size)
{ if (size==1) return；
int t=tile++，// L型骨牌数
s=size／2； // 分割棋盘
//覆盖左上角子棋盘
if (dr< tr +s && dc < tc+S)
//特殊方格在此棋盘中
ChessBoard(tr, tc, dr,dc,S)；
else{//此棋盘中无特殊方格
//用t号L型骨牌覆盖右下角
Board[tr+s-1][tc+s-1]=t；
//覆盖其余方格
Chessboard(tr，tc，tr+s-1，tc+s-l，s)；}
//覆盖右上角子棋盘
if (dr <= tr +s && dc >= tc+S)
//特殊方格在此棋盘中
ChessBoard(tr，tc+s ，dr，dc，S)；
else{//此棋盘中无特殊方格
//用t号骨牌覆盖左下角
Board[tr+s-1][tc+s]=t；
//覆盖其余方格
Chessboard(tr，tc+s，tr+s-1，tc+s，s)；}
………………...
void outputBoard( int size)
{ for inti=0;i<size;i++){
for intj=0 ;j<size ;j++)；
cout<<setw(5)<<board [i][j];
cout<<endl;}}
