声明：本文使用的代码和例子的来源：《计算机算法设计与分析》（王晓东编著，电子工业出版社）。我对代码做了少许修改，使可以在tc的图形模式下看到题目的结果。

题目：在一个(2^k)*(2^k)个方格组成的棋盘上，有一个特殊方格与其他方格不同，称为特殊方格，称这样的棋盘为一个特殊棋盘。现在要求对棋盘的其余部分用L型方块填满（注：L型方块由3个单元格组成。即围棋中比较忌讳的愚形三角，方向随意），切任何两个L型方块不能重叠覆盖。L型方块的形态如下：

■■     ■■      ■        ■
■   ，    ■ ，   ■■ ， ■■

题目的解法使用分治法，即子问题和整体问题具有相同的形式。我们对棋盘做一个分割，切割一次后的棋盘如图1所示，我们可以看到棋盘被切成4个一样大小的子棋盘，特殊方块必定位于四个子棋盘中的一个。假设如图1所示，特殊方格位于右上角，我们把一个L型方块（灰色填充）放到图中位置。这样对于每个子棋盘又各有一个“特殊方块”，我们对每个子棋盘继续这样分割，知道子棋盘的大小为1为止。
    用到的L型方块需要（4^k-1)/3 个，算法的时间是O（4^k)，是渐进最优解法。
    本题目的C语言的完整代码如下（TC2.0下调试），运行时，先输入k的大小，(1<=k<=6)，然后分别输入特殊方格所在的位置(x,y), 0<=x,y<=(2^k-1)。程序将绘制出覆盖后的棋盘，运行效果截图如图2所示。

/*

 * 用分治法，一个棋盘，提供一个特殊方格用黑色填充，其余用L型方块填满。

 */
#include <stdio.h>
#include <graphics.h>
/*#include <cpyscr.h>*/

#define N 64
#define BoardLeft 2
#define BoardTop    2

int Board[N][N]; /*棋盘*/
int tile;/*全局性质的L图形编号*/
int CellSize=10;/*网格大小*/
int BorderColor=LIGHTGRAY;

/*用指定颜色填充一个单元格！*/
void PutCell(int x,int y,int color)
{
    setfillstyle(SOLID_FILL,color);
    rectangle(BoardLeft+x*CellSize,BoardTop+y*CellSize,BoardLeft+(x+1)*CellSize,BoardTop+(y+1)*CellSize);
    floodfill(BoardLeft+x*CellSize+CellSize/2,BoardTop+y*CellSize+CellSize/2,BorderColor);
}
/*绘制L方块，（cx,cy）是L方块的中心点CELL坐标，pos从1到4，表示位于特殊方块位于哪个角（即缺失的一角位置）*/
void PutBlock(int cx,int cy,int pos)
{
    int x,y,t=CellSize;/*方块起始点像素坐标*/
    x=BoardLeft+cx*CellSize;
    y=BoardTop+cy*CellSize;
    moveto(x,y);/*移动到中心点*/
    switch(pos)
    {
        case 1:/*左上角缺*/
            lineto(x,y-t);
            lineto(x+t,y-t);
            lineto(x+t,y+t);
            lineto(x-t,y+t);
            lineto(x-t,y);
            break;
        case 2:/*右上角缺*/
            lineto(x+t,y);
            lineto(x+t,y+t);
            lineto(x-t,y+t);
            lineto(x-t,y-t);
            lineto(x,y-t);
            break;
        case 3:/*左下角缺*/
            lineto(x-t,y);
            lineto(x-t,y-t);
            lineto(x+t,y-t);
            lineto(x+t,y+t);
            lineto(x,y+t);
            break;
        case 4:/*右下角缺*/
            lineto(x,y+t);
            lineto(x-t,y+t);
            lineto(x-t,y-t);
            lineto(x+t,y-t);
            lineto(x+t,y);
            break;
    }
    lineto(x,y);/*回到闭合点！*/
}

/*初始化图形模式*/
void InitGraph()
{
    int gdriver=DETECT,gmode;
    initgraph(&gdriver,&gmode,"");
    setcolor(BorderColor);
}
/*关闭图形模式*/
void CloseGraph()
{
    closegraph();
}

    /*打印棋盘*/
void PrintBoard(int size)
{
    int i,j;
    clrscr();
    for(j=0;j<size;j++)
    {
        for(i=0;i<size;i++)
        {
            printf("%2d ",Board[i][j]);
        }
        printf("\n");
    }
    printf("\n--------------------------------\n");
    printf("size=%d;\n");
}

/*left,top：方块的左上角坐标，x,y：特殊方块的坐标 size:当前的子棋盘大小*/
void ChessBoard(int left,int top,int x,int y,int size)
{
    int i,t,s,pos;/*t是方块的编号，s是棋盘的一半尺寸！(size/2),pos表示方块位于哪一角 */
    if(size==1)
        return;
    t=tile++;/*当前L行方块的编号！递增*/
    s=size/2;

    /*------------处理左上角----------*/
    if(x<left+s && y<top+s)
    {
        ChessBoard(left,top,x,y,s);/*设置位于左上角的标识*/
        pos=1;
    }
    else
    {
        Board[left+s-1][top+s-1]=t;          /*不在左上角*/
        ChessBoard(left,top,left+s-1,top+s-1,s);
    }

    /*------------处理右上角----------*/
    if(x>=left+s && y<top+s)
    {
        ChessBoard(left+s,top,x,y,s);
        pos=2;
    }
    else
    {
        Board[left+s][top+s-1]=t;/*不在右上角*/
        ChessBoard(left+s,top,left+s,top+s-1,s);
    }

    /*------------处理左下角----------*/
    if(x<left+s && y>=top+s)
    {
        ChessBoard(left,top+s,x,y,s);
        pos=3;
    }
    else
    {
        Board[left+s-1][top+s]=t;
        ChessBoard(left,top+s,left+s-1,top+s-1,s);
    }

    /*------------处理右下角----------*/
    if(x>=left+s && y>=top+s)
    {
        ChessBoard(left+s,top+s,x,y,s);
        pos=4;
    }
    else
    {
        Board[left+s][top+s]=t;
        ChessBoard(left+s,top+s,left+s,top+s,s);
    }
    /*画出当前的L方块*/
    PutBlock(left+s,top+s,pos);
}


void main()
{
    int size,k,x,y,i,j;
    printf("please input k=? (k should not more than 6, boardsize=2^k ): \n");
    scanf("%d",&k);
    size=1<<k;
    printf("please input position of the special cell. x=? (not more than %d): \n",size-1);
    scanf("%d",&x);
    printf("please input position of the special cell. y=? (not more than %d): \n",size-1);
    scanf("%d",&y);
    if(k<0 || k>6 || x<0 || x>(size-1) || y<0 || y>(size-1))
    {
        printf("Input invalid!\n");
        return;
    }

    InitGraph();
    tile=1;

    Board[x][y]=0;
    /*绘制特殊方块！*/
    PutCell(x,y,RED);
    ChessBoard(0,0,x,y,size);
    /*CopyScreen("c:\\tc\\temp\\chess.bmp",0,0,400,400);*/
    getch();
    CloseGraph();
}

[[it] 本帖最后由 hoodlum1980 于 2008-3-22 20:51 编辑 [/it]]