问题描述
有一个x（k>0）的棋盘，恰好有一个方格与其他方格不同，称之为特殊方格。现在要用如下图所示的L形骨牌覆盖除了特殊方格以外的其他全部方格，骨牌可以任意旋转，并且任何两个骨牌不能重复。请给出一种覆盖方式。
下面给出两个例子：(假设特殊方格是白色的）
k=2k=3问题求解
因为方格数=x=，L形骨牌个数=（-1—）/ 3 。以上面的第2个例子举例说明：特殊方格在第8行，第3列，因此特殊方格的右下角（即绿色的L形骨牌）仅一种表示形式——（大家可以尝试一下，其他方法左边两列能否正确处理）。绿色放置之后对于左下角的4x4的正方形来说，特殊方格位于它的第四象限，所以橙色的L形骨牌仅一种表现形式。对于其他的三个象限来说可以将橙色作为它们的特殊方格，以此类推，所有的排列方式即可确定。
因此将原问题分为四个象限求解，且若象限的大小超过4个小方格，即可继续划分（可进行递归调用）。将原棋盘大小设为 size=x,每次划分后的棋盘大小设为 s=size/2; 特殊方格的坐标记为(dr,dc) ;象限的起点（即左上角）记为 (tr,tc) ！！！牢记这一点！！！接着我们将其特殊格子所在的位置分为四种情况：
当其在第一象限（即右上象限）：将右上象限填满之后，以左下角作为特殊方格进行处理
if(dr<tr+s && dc>=tc+s)Solve(tr,tc+s,dr,dc,s);else{board[tr+s-1][tc+s]=t;Solve(tr,tc+s,tr+s-1,tc+s,s);}
当其在第二象限（即左上象限）：将左上象限填满之后，以右下角作为特殊方格进行处理
if(dr<tr+s && dc<tc+s)Solve(tr,tc,dr,dc,s);else{board[tr+s-1][tc+s-1]=t;Solve(tr,tc,tr+s-1,tc+s-1,s);}
当其在第三象限（即左下象限）：将左下象限填满之后，以右上角作为特殊方格进行处理
if(dr>=tr+s && dc<tc+s)Solve(tr+s,tc,dr,dc,s);else{board[tr+s][tc+s-1]=t;Solve(tr+s,tc,tr+s,tc+s-1,s);}
当其在第四象限（即右下象限）：将右下象限填满之后，以左上角作为特殊方格进行处理
if(dr>=tr+s && dc>=tc+s)Solve(tr+s,tc+s,dr,dc,s);else{board[tr+s][tc+s]=t;Solve(tr+s,tc+s,tr+s,tc+s,s);}
代码
#include <iostream>#include <cmath>#include <iomanip>//setw()所在的头文件#define MAX 1025using namespace std;int k;int x,y;//输入的特殊方格的位置int tile=1;int board[MAX][MAX]; //记录L形骨牌的编号void Solve(int tr,int tc,int dr,int dc,int size){if(size==1) return;int t = tile;int s = size/2;tile++;//考虑左上象限if(dr<tr+s && dc<tc+s)Solve(tr,tc,dr,dc,s);else{board[tr+s-1][tc+s-1]=t;Solve(tr,tc,tr+s-1,tc+s-1,s);}//考虑右上象限if(dr<tr+s && dc>=tc+s)Solve(tr,tc+s,dr,dc,s);else{board[tr+s-1][tc+s]=t;Solve(tr,tc+s,tr+s-1,tc+s,s);}//考虑左下象限if(dr>=tr+s && dc<tc+s)Solve(tr+s,tc,dr,dc,s);else{board[tr+s][tc+s-1]=t;Solve(tr+s,tc,tr+s,tc+s-1,s);}//考虑右下象限if(dr>=tr+s && dc>=tc+s)Solve(tr+s,tc+s,dr,dc,s);else{board[tr+s][tc+s]=t;Solve(tr+s,tc+s,tr+s,tc+s,s);}}int main(){cout << "Input k(k<=10): ";cin>>k;cout<<"Input x,y: ";cin>>x>>y;int size = pow(2,k);Solve(0,0,x,y,size);for(int i=0; i<size; i++){for(int j=0; j<size; j++)cout<<setw(4)<<setfill(' ')<<board[i][j];cout<<endl;}return 0;}
参考资料：《算法设计与分析》第2版
如果觉得《棋盘覆盖问题（分治法）》对你有帮助，请点赞、收藏，并留下你的观点哦！
