棋盤覆蓋問題課件

棋盤覆蓋問題問題描述（一）在一個

（k≥0）個方格組成的棋盤中，恰有一個方格與其他方格不同，稱該方格為特殊方格，顯然，特殊方格在棋盤中出現(xiàn)的位置有中情形，因而有中不同的棋盤(如圖(a))。(a)

k=2時的一種棋盤問題描述（二）

棋盤覆蓋問題要求用如圖(b)所示的L型骨牌覆蓋給定棋盤上除特殊方格以外的所有方格，且任何2個L型骨牌不得重疊覆蓋。(b)4種不同形狀的L型骨牌問題分析（一）

用分治策略，可以設(shè)計解棋盤覆蓋問題的一個簡潔算法

(1)當k>0時,將棋盤分割為4個子棋盤(如下圖(c))；2k-1×2k-12k-1×2k-12k-1×2k-12k-1×2k-1特殊方格必位于4個子棋盤之一，其余3個子棋盤中無特殊方格。(c)棋盤分割問題分析（二）

(2)用一個L型骨牌覆蓋這3個較小棋盤的結(jié)合處。(如圖(d))這3個子棋盤上被L型骨牌覆蓋的方格就成為該棋盤上的殘缺方格,原問題轉(zhuǎn)化為4個較小規(guī)模的棋盤覆蓋問題。遞歸地使用這種分割，直至棋盤簡化為11棋盤。(d)

構(gòu)造相同子問題詳細過程圖解如下棋盤中有一個特殊方格第一次分割第二次分割第三次分割第四次分割為1×1棋盤第一次分割后子棋盤的覆蓋結(jié)果問題求解下面介紹棋盤覆蓋問題中數(shù)據(jù)結(jié)構(gòu)的設(shè)計：（1）棋盤：用二維數(shù)組Board[size][size]表示一個棋盤，Board[0][0]是棋盤的左上角方格。其中，size=

。為了在遞歸處理的過程中使用同一個棋盤，將數(shù)組Board設(shè)為全局變量；（2）子棋盤：在棋盤數(shù)組Board[size][size]中，由子棋盤左上角的下標tr、tc和棋盤邊長s表示；（3）特殊方格：用Board[dr][dc]表示，dr和dc是該特殊方格在棋盤數(shù)組Board中的下標；（4）L型骨牌：一個的棋盤中有一個特殊方格，所以用到L型骨牌的個數(shù)為(

-1)/3將所有L型骨牌從1開始連續(xù)編號，用一個全局整型變量tile表示，其初始值為0。算法的輸入?yún)?shù)是：tr:棋盤左上角方格的行號tc:棋盤左上角方格的列號dr:特殊方格所在的行號dc:特殊方格所在的列號size:size=,棋盤規(guī)格為dcdrtrtcsize棋盤覆蓋問題中的數(shù)據(jù)結(jié)構(gòu)算法—棋盤覆蓋

實現(xiàn)這種分治策略的算法ChessBoard如下：voidChessBoard(inttr,inttc,intdr,intdc,intsize)//tr和tc是棋盤左上角的下標，dr和dc是特殊方格的下標，//size是棋盤的大小，t已初始化為0{if(size==1)return;//棋盤只有一個方格且是特殊方格

t++;//L型骨牌號

s=size/2;//劃分棋盤

//覆蓋左上角子棋盤

if(dr<tr+s&&dc<tc+s)//特殊方格在左上角子棋盤中

ChessBoard(tr,tc,dr,dc,s);//遞歸處理子棋盤

else{//用t號L型骨牌覆蓋右下角，再遞歸處理子棋盤

board[tr+s-1][tc+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);//遞歸處理子棋盤else{//用t號L型骨牌覆蓋左下角，再遞歸處理子棋盤board[tr+s-1][tc+s]=t;ChessBoard(tr,tc+s,tr+s-1,tc+s,s);}//覆蓋左下角子棋盤if(dr>=tr+s&&dc<tc+s)//特殊方格在左下角子棋盤中ChessBoard(tr+s,tc,dr,dc,s);//遞歸處理子棋盤else{//用t號L型骨牌覆蓋右上角，再遞歸處理子棋盤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{//用t號L型骨牌覆蓋左上角，再遞歸處理子棋盤board[tr+s][tc+s]=t;ChessBoard(tr+s,tc+s,tr+s,tc+s,s);}}時間復雜度分析算法分析:設(shè)T(k)為覆蓋棋盤的時間