用分治法求解棋盤覆蓋問題

1、棋盤覆蓋問題問題描述:在一個(gè)2kX2k厶卻丿個(gè)方格組成的棋盤中，恰有一個(gè)方格與其他方格不同，稱該方格為特殊方格。顯然，特殊方格在棋盤中出現(xiàn)的位置有孝中情形，因而有4*中不同的棋盤， 圖（a）所示是k=2時(shí)"種棋盤中的一個(gè)。棋盤覆蓋問題要求用圖（b）所示的4中不同形狀的L型骨牌覆蓋給定棋盤上除特殊方格以外的所有方格，且熱河亮哥L型骨牌不得重復(fù)覆蓋。圖（b）圖（a）問題分析：K>0時(shí)，可將2kX2k的棋盤劃分為4個(gè)2X21的子棋盤。這樣劃分后，由于原棋盤只有一個(gè)特殊方格，所以，這4個(gè)子棋盤中只有2個(gè)子棋盤中有特殊方格，其余3個(gè)子棋盤中 沒有特殊方格。為了將這3個(gè)沒有特殊方格的子棋盤

2、轉(zhuǎn)化成為特殊棋盤，以便采用遞歸方法求解，可以用一個(gè)I型骨牌覆蓋這3個(gè)較小的棋盤的會(huì)合處，從而將原問題轉(zhuǎn)化為4個(gè)較小 規(guī)模的棋盤覆蓋問題。遞歸地使用這種劃分策略，直至將棋盤分割為1X2的子棋盤。問題求解：卜面介紹棋盤覆蓋問題中數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)。（1）棋盤：可以用一個(gè)二維數(shù)組boardsizesize表示一個(gè)棋盤，其中血*2匕為了 在遞歸處理的過程中使用同一個(gè)棋盤，將數(shù)組board設(shè)為全局變量。（2）子棋盤：整個(gè)棋盤用二維數(shù)組boardSizesize表示，其中的子棋盤由棋盤左上 角的下標(biāo)tr tc和棋盤大小$表示。（3）特殊方格：用boarddrdc表示特殊方格，dr和de是該特殊方格在二維數(shù)組

3、board中的下標(biāo)。（4）型骨牌：一個(gè)2kX2k的棋盤中有一個(gè)特殊方格，所以，用到型骨牌的個(gè)數(shù) 為（1） /3,將所有I型骨牌從2開始連續(xù)編號(hào)，用一個(gè)全局變量切£表示。c語(yǔ)言源碼：/author:彭洪偉*studentlD:0950310006*class:計(jì)科1班problem:分治法解決棋盤覆蓋問題*/#include <stdio.h>#include <math.h>int tile=l; /記錄骨牌的型號(hào)int board2020=0; 存儲(chǔ)棋盤被覆蓋的情況void ChessBoardfint trjnt tc,int dr,int dcjnt s

4、ize)/tr和tc是棋盤左上角的下標(biāo),dr和de是特殊方格的下標(biāo),size是棋盤的人小 int t=0;int s;if (size=l)return;t=tile+;s=size/2; 劃分棋盤覆蓋左上角棋盤if (dr<tr+s&&dc<tc+s) 特殊方格在棋盤的左上角ChessBoard(tr,tc,di;dc,s);elseboa rdtr+s-ltc+s-l=t;ChessBoard(ti;tc，tr+s :l,tc+sJ,s);覆蓋右上角棋盤if (dr<tr+s&&dc>=tc+s) 特殊方格在棋盤的右上角ChessBo

5、ardftotc+sGds);elseboa rd tr+s-ltc+s =t;ChessBoardftGtc+sr+s-l.tc+s);覆蓋左下角棋盤if (dr>=tr+s&&dc<tc+s) 特殊方格在棋盤的左卞角ChessBoard(tr+s,tc,dr;dc，s);elseboardtr+stc+s-l=t;ChessBoardftr+str+sc+s-l.s);覆蓋右下角棋盤if (dr>=tr+s&&dcxtc+s) /特殊方格在棋盤的右下角 ChessBoard(tr+s,tc+s,dr;dC"S);elseboa r

6、d tr+s tc+s=t;ChessBoard(tr+s,tc+s,tr+s，tc+s,s);int main()int k，x,y;printf("請(qǐng)輸入棋盤的規(guī)模K：")；scanf(“d",&k);printf("請(qǐng)輸入特殊方格的下標(biāo)x,y：");scanf(H%d %cT：&x,&y);ChessBoard(0/0,x/yzpow(2,k);for(int i=0; i<pow(2,k); i+)for (int j=0; j<pow(2,k); j+)printf(”"4cT：boardij); printfCV);return 0;CA運(yùn)行結(jié)果截圖：nF:StudyAlgorithm