分治算法棋盘覆盖题目：在一个(2^k)*(2^k)个方格组成的棋盘上，有一个特殊方格与其他方格不同，称为特殊方格，称这样的棋盘为一个特殊棋盘

我们要求对棋盘的其余部分用L型方块填满（注：L型方块由3个单元格组成

即围棋中比较忌讳的愚形三角，方向随意），且任何两个L型方块不能重叠覆盖

L型方块的形态如下：题目的解法使用分治法，即子问题和整体问题具有相同的形式

我们对棋盘做一个分割，我们可以看到棋盘被切成4个一样大小的子棋盘，特殊方块必定位于四个子棋盘中的一个

这样对于每个子棋盘又各有一个“特殊方块”，我们对每个子棋盘继续这样分割，直到子棋盘的大小为1为止

用到的L型方块需要（4^k-1)/3 个，算法的时间是O（4^k)，是渐进最优解法

本题目的C语言的完整代码如下（TC2.0下调试），运行时，先输入k的大小，(1<=k<=6)，然后分别输入特殊方格所在的位置(x,y), 0<=x,y<=(2^k-1)

#include//#include//#includeint title=1;int board;void chessBoard(inttr,inttc,intdr,intdc,intsize){    int s,t;if(size==1) return;    t=title++;    s=size/2;    if(dr=tc+s)        chessBoard(tr,tc+s,dr,dc,s);    else    {        board[tr+s-1][tc+s]=t;        chessBoard(tr,tc+s,tr+s-1,tc+s,s);    }    if(dr>=tr+s&&dc=tr+s&&dc>=tc+s)        chessBoard(tr+s,tc+s,dr,dc,s);    else    {        board[tr+s][tc+s]=t;        chessBoard(tr+s,tc+s,tr+s,tc+s,s);    }}void main(){    int dr=0,dc=0,s=1,i=0,j=0;    printf("printinthesizeofchess: ");    scanf("%d",&s);    printf("printinspecalpointx,y: ");    scanf("%d%d",&dr,&dc);    if(dr

以上内容由大学时代综合整理自互联网，实际情况请以官方资料为准。