分治算法之 棋盘覆盖问题（完整代码实现）

我在这里是用了一个简化的方式，只是代码简化，还是分治递归思想。一分为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;}}