1、分治法棋盤覆蓋聲明：本文使用的代碼和例子的來源：計(jì)算機(jī)算法設(shè)計(jì)與分析（王曉東編著，電子工業(yè)出版社）。我對(duì)代碼做了少許修改，使可以在 tc的圖形模式下看到題目的結(jié)果。題目：在一個(gè)（2"）*（2"）個(gè)方格組成的棋盤上，有一個(gè)特殊方格與其他方格不同，稱為特殊方格，稱這樣的棋盤為一個(gè)特殊棋盤。現(xiàn)在要求對(duì)棋盤的其余部分用L型方塊填滿（注：L型方塊由3個(gè)單元格組成。即圍棋中比較忌諱的愚形三角，方向隨意），切任何兩個(gè)L型方塊不能重疊覆蓋。L型方塊的形態(tài)如下：題目的解法使用分治法，即子問題和整體問題具有相同的形式。我們對(duì)棋盤做一個(gè)分割，切 割一次后的棋盤如圖 1所示，我們可以看到棋盤被切成

2、4個(gè)一樣大小的子棋盤，特殊方塊必定位于四個(gè)子棋盤中的一個(gè)。假設(shè)如圖1所示，特殊方格位于右上角，我們把一個(gè)L型方塊（灰色填充）放到圖中位置。這樣對(duì)于每個(gè)子棋盤又各有一個(gè)特殊方塊：我們對(duì)每個(gè)子棋盤繼續(xù)這樣分割，知道子棋盤的大小為1為止。用到的L型方塊需要（4"-1）/3個(gè)，算法的時(shí)間是 O （4"），是漸進(jìn)最優(yōu)解法。本題目的C語言的完整代碼如下（TC2.0下調(diào)試），運(yùn)行時(shí)，先輸入 k的大小，（1<=k< =6）,然后分別輸入特殊方格所在的位置（x,y）, 0<=x,y<=（2"-1）。程序?qū)⒗L制出覆蓋后的棋盤，運(yùn)行效果截圖如圖2所示。此程序在T

3、C下課成功運(yùn)行。VC下缺少頭文件<graphics.h> ,編譯時(shí)會(huì)出現(xiàn)錯(cuò)誤。#include <stdio.h>#include <graphics.h>/*#include <cpyscr.h>*/# define N 64# define BoardLeft 2# define BoardTop 2int BoardNN; /* 棋盤*/int tile;/* 全局性質(zhì)的L圖形編號(hào)*/ int CellSize=10;/* 網(wǎng)格大小*/ int BorderColor=LIGHTGRAY;/*用指定顏色填充一個(gè)單元格！*/void PutC

4、ell(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+Cel lSize/2,BorderColor);/*繪制L方塊，(cx,cy )是L方塊的中心點(diǎn)CELLOS, pos從1到4,表示位 于特殊方塊位于哪個(gè)角(

5、即缺失的一角位置) */void PutBlock(int cx,int cy,int pos)int x,y,t=CellSize;/*方塊起始點(diǎn)像素坐標(biāo)*/x=BoardLeft+cx*CellSize;y=BoardTop+cy*CellSize;moveto(x,y);/* 移動(dòng)到中心點(diǎn)*/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,

6、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);/* 回到閉合點(diǎn)！ */*初始化圖形模式*/void InitGrap

7、h()int gdriver=DETECT,gmode;initgraph(&gdriver,&gmode,"");setcolor(BorderColor);/*關(guān)閉圖形模式*/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皿); printf("n");printf("n

8、An");printf("size=%d;n");/*left,top :方塊的左上角坐標(biāo)，x,y :特殊方塊的坐標(biāo)size:當(dāng)前的子棋盤大 小*/void ChessBoard(int left,int top,int x,int y,int size)int i,t,s,pos;/*t是方塊的編號(hào)，s是棋盤的一半尺寸！ (size/2),pos 表示方塊位于哪一角*/if(size=1)return;t=tile+;/* 當(dāng)前L行方塊的編號(hào)！遞增*/s=size/2;/* 處理左上角*/if(x<left+s && y<top+s)

9、ChessBoard(left,top,x,y,s);/*設(shè)置位于左上角的標(biāo)識(shí) */pos=1; elseBoardleft+s-1top+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; elseBoardleft+stop+s-1=t;/*不在右上角 */ChessBoard(left+s,top,left+s,top+s-1,s);/* 處理左下角*/if(x

10、<left+s && y>=top+s)ChessBoard(left,top+s,x,y,s);pos=3; elseBoardleft+s-1top+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;elseBoardleft+stop+s=t;ChessBoard(left+s,top+s,left+s,top+s,s);/* 畫出當(dāng)前的L方塊*/P

11、utBlock(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=2Ak)：n")；scanf("%d",&k);size=1<<k;printf("please input position of the special cell. x=? (not morethan %d): n",size-1);scanf("%d",&a

12、mp;x);printf("please input position of the special cell. y=? (not morethan %d): n",size-1);scanf("%d",&y);if(k<0 11k>6 | x<0 | x>(size-1) | y<0 | y>(size-1)printf("Input invalid!n");return;InitGraph();tile=1;Boardxy=0;/*繪制特殊方塊！ */PutCell(x,y,RED);C

13、hessBoard(0,0,x,y,size);/*CopyScreen("c:tctempchess.bmp",0,0,400,400);7getch();CloseGraph();2 . #include"stdio.h"#include<graphics.h>#include<dos.h>#include<math.h>int tile=1;int avg;int basex,basey;void chessboard(int tr,int tc,int dr,int dc,int size)/*加了一個(gè) int

14、 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)<tr+s*avg&&(dc*avg+basey)<tc+s*avg) chessboard(tr,tc,dr,dc,s);elsesetf

15、illstyle(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)<tr+s*avg&&(dc*avg+basey)>=tc+s*avg) chessboard(tr,tc+s*avg,dr,dc,s);elsesetfillstyle(1,t);bar(tr+(s-1)*avg,tc+s*avg,tr+s*avg,tc+(s+1)*avg);/*在這力口了 一

16、個(gè) 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)<tc+s*avg) chessboard(tr+s*avg,tc,dr,dc,s);elsesefillstyle(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-

17、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);elsesetfillstyle(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

18、;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 函數(shù) */ outtextxy(60,60,"designer:zhoumin

19、gjiang 25/10/2002");setbkcolor(BLACK);setcolor(RED);printf("nnn");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);lin

20、e(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 <stdio.h>#include <conio.h>#include <math.h>int title=1;int board6464;void chessBoard(int tr,int tc,int dr,int dc,int size)(int s,t;if(size=1) return;t=title+;s=size/2;if(dr<tr+s && dc<tc+s)chessBoard(tr,tc,dr,dc,s);elseboardtr+s-1tc+s-1=t;chessBoard(tr,tc,tr+s-1,tc+s-1,s);if(dr<tr+s && dc>=tc+s)chessBoard(tr,tc+s,dr,dc,s);elseboar