棋盘覆盖问题.docx
《棋盘覆盖问题.docx》由会员分享，可在线阅读，更多相关《棋盘覆盖问题.docx（13页珍藏版）》请在冰点文库上搜索。
棋盘覆盖问题
分治法棋盘覆盖
声明：
本文使用的代码和例子的来源：
《计算机算法设计与分析》（王晓东编著，电子工业出版社）。
我对代码做了少许修改，使可以在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所示。
[此程序在TC下课成功运行。
VC下缺少头文件
，编译时会出现错误。
]
#include
#include
/*#include*/
#defineN64
#defineBoardLeft2
#defineBoardTop 2
intBoard[N][N];/*棋盘*/
inttile;/*全局性质的L图形编号*/
intCellSize=10;/*网格大小*/
intBorderColor=LIGHTGRAY;
/*用指定颜色填充一个单元格！
*/
voidPutCell（intx,inty,intcolor）
{
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，表示位于特殊方块位于哪个角（即缺失的一角位置）*/
voidPutBlock（intcx,intcy,intpos）
{
intx,y,t=CellSize;/*方块起始点像素坐标*/
x=BoardLeft+cx*CellSize;
y=BoardTop+cy*CellSize;
moveto（x,y）;/*移动到中心点*/
switch（pos）
{
case1:
/*左上角缺*/
lineto（x,y-t）;
lineto（x+t,y-t）;
lineto（x+t,y+t）;
lineto（x-t,y+t）;
lineto（x-t,y）;
break;
case2:
/*右上角缺*/
lineto（x+t,y）;
lineto（x+t,y+t）;
lineto（x-t,y+t）;
lineto（x-t,y-t）;
lineto（x,y-t）;
break;
case3:
/*左下角缺*/
lineto（x-t,y）;
lineto（x-t,y-t）;
lineto（x+t,y-t）;
lineto（x+t,y+t）;
lineto（x,y+t）;
break;
case4:
/*右下角缺*/
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）;/*回到闭合点！
*/
}
/*初始化图形模式*/
voidInitGraph（）
{
intgdriver=DETECT,gmode;
initgraph（&gdriver,&gmode,""）;
setcolor（BorderColor）;
}
/*关闭图形模式*/
voidCloseGraph（）
{
closegraph（）;
}
/*打印棋盘*/
voidPrintBoard（intsize）
{
inti,j;
clrscr（）;
for（j=0;j {
for（i=0;i {
printf（"%2d",Board[i][j]）;
}
printf（"\n"）;
}
printf（"\n--------------------------------\n"）;
printf（"size=%d;\n"）;
}
/*left,top：
方块的左上角坐标，x,y：
特殊方块的坐标size:
当前的子棋盘大小*/
voidChessBoard（intleft,inttop,intx,inty,intsize）
{
inti,t,s,pos;/*t是方块的编号，s是棋盘的一半尺寸！
（size/2）,pos表示方块位于哪一角*/
if（size==1）
return;
t=tile++;/*当前L行方块的编号！
递增*/
s=size/2;
/*------------处理左上角----------*/
if（x {
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 {
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=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）;
}
voidmain（）
{
intsize,k,x,y,i,j;
printf（"pleaseinputk=?
（kshouldnotmorethan6,boardsize=2^k）:
\n"）;
scanf（"%d",&k）;
size=1< printf（"pleaseinputpositionofthespecialcell.x=?
（notmorethan%d）:
\n",size-1）;
scanf（"%d",&x）;
printf（"pleaseinputpositionofthespecialcell.y=?
（notmorethan%d）:
\n",size-1）;
scanf（"%d",&y）;
if（k<0||k>6||x<0||x>（size-1）||y<0||y>（size-1））
{
printf（"Inputinvalid!
\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（）;
}
2.#include"stdio.h"
#include
#include
#include
int tile=1;
int avg;
int basex,basey;
void chessboard（int tr,int tc,int dr,int dc,int size）/*加了一个int tc*/
{
int s,t;
if（size==1）return;
t=tile++;
s=size/2;
delay（150000）;
setfillstyle（7,1）;
sound（500）;
delay（1500）;
sound（400）;
delay（1500）;
nosound（）;
bar（dr*avg+basex,dc*avg+basey,（dr+1）*avg+basex,（dc+1）*avg+basey）;
if（（dr*avg+basex） chessboard（tr,tc,dr,dc,s）;
else
{
setfillstyle（1,t）;
bar（tr+（s-1）*avg,tc+（s-1）*avg,tr+s*avg,tc+s*avg）;
chessboard（tr,tc,（tr-basex）/avg+s-1,（tc-basey）/avg+s-1,s）;
}
if（（dr*avg+basex）=tc+s*avg）
chessboard（tr,tc+s*avg,dr,dc,s）;
else
{
setfillstyle（1,t）;
bar（tr+（s-1）*avg,tc+s*avg,tr+s*avg,tc+（s+1）*avg）;/*在这加了一个tr+s*avg*/
chessboard（tr,tc+s*avg,（tr-basex）/avg+s-1,（tc-basey）/avg+s,s）;
}
if（（dr*avg+basex）>=tr+s*avg&&（dc*avg+basey） chessboard（tr+s*avg,tc,dr,dc,s）;
else
{
setfillstyle（1,t）;
bar（tr+s*avg,tc+（s-1）*avg,tr+（s-1）*avg,tc+s*avg）;
chessboard（tr+s*avg,tc,（tr-basex）/avg+s,（tc-basey）/avg+s-1,s）;
}
if（（dr*avg+basex）>=tr+s*avg&&（dc*avg+basey）>=tc+s*avg）
chessboard（tr+s*avg,tc+s*avg,dr,dc,s）;
else
{
setfillstyle（1,t）;
bar（tr+s*avg,tc+s*avg,tr+（s+1）*avg,tc+（s+1）*avg）;
chessboard（tr+s*avg,tc+s*avg,（tr-basex）/avg+s,（tc-basey）/avg+s,s）;
}
}
main（）
{
int size,k;
int dr,dc,tr,tc;
int endx,endy;
int i;
double x,y;
int gdriver=DETECT;
int gmode=VGA;
initgraph（&gdriver,&gmode,""）;
basex=300,basey=100;
endx=basex+320;
endy=basey+320;
cleardevice（）;
setcolor（12）;
settextstyle（2,0,8）;
outtextxy（20,20,"zhoumingjiang\n"）;/*改成了outtextxy函数~~*/
outtextxy（60,60,"designer:
zhoumingjiang 25/10/2002"）;
setbkcolor（BLACK）;
setcolor（RED）;
printf（"\n\n\n"）;
printf（" please input k:
"）;
scanf（"%d",&k）;
x=2;
y=k;
size=pow（x,y）;
avg=320/size;
rectangle（basex,basey,endx,endy）;
for（i=0;i<=size;i++）
{
setlinestyle（1,1,6）;
line（basex,basey+i*avg,endx,basey+i*avg）;
line（basex+i*avg,basey,basex+i*avg,endy）;
}
printf（" please input dr,dc:
"）;
scanf（"%d,%d",&dc,&dr）;
tr=basex;
tc=basey;
chessboard（tr,tc,dr,dc,size）;
}_
3.棋盘覆盖（C语言）
#include
#include
#include
inttitle=1;
intboard[64][64];
voidchessBoard（inttr,inttc,intdr,intdc,intsize）
{
ints,t;
if（size==1）return;
t=title++;
s=size/2;
if（dr chessBoard（tr,tc,dr,dc,s）;
else
{
board[tr+s-1][tc+s-1]=t;
chessBoard（tr,tc,tr+s-1,tc+s-1,s）;
}
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 chessBoard（tr+s,tc,dr,dc,s）;
else
{
board[tr+s][tc+s-1]=t;
chessBoard（tr+s,tc,tr+s,tc+s-1,s）;
}
if（dr>=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）;
}
}
voidmain（）
{ intdr=0,dc=0,s=1,i=0,j=0;
printf（"printinthesizeofchess:
\n"）;
scanf（"%d",&s）;
printf（"printinspecalpointx,y:
\n"）;
scanf（"%d%d",&dr,&dc）;
if（dr {
chessBoard（0,0,dr,dc,s）;
for（i=0;i {
for（j=0;j {
printf（"%4d",board[i][j]）;
}
printf（"\n"）;
}
}
else
printf（"thewrongspecalpoint!
!
\n"）;
getch（）;
}
升级会员 