用分治法求解棋盤(pán)覆蓋問(wèn)題-全文預(yù)覽
【正文】 r,tc,dr,dc,s)。 t=tile++。 //記錄骨牌的型號(hào) int board[20][20]={0}。 （ 2） 子棋盤(pán)：整個(gè)棋盤(pán)用二維數(shù)組 board[size][size]表示，其中的子棋盤(pán)由棋盤(pán)左上角的下標(biāo) tr、 tc 和棋盤(pán)大小 s 表示。遞歸地使用這種劃分策略，直至將棋盤(pán)分割為 1 1 的子棋盤(pán)。棋盤(pán)覆蓋問(wèn)題要求用圖（ b）所示的 4 中不同形狀的 L型骨牌覆蓋給定棋盤(pán)上除特殊方格以外的所有方格，且熱河亮哥 L型骨牌不得重復(fù)覆蓋。顯然，特殊方格在棋盤(pán)中出現(xiàn)的位置有 4k中情形，因而有 4k中不同的棋盤(pán)，圖（ a）所示是 k=2 時(shí) 16 種棋盤(pán)中的一個(gè)。為了將這 3 個(gè)沒(méi)有特殊方格的子棋盤(pán)轉(zhuǎn)化成為特殊棋盤(pán)，以便采用遞歸方法求解，可以用一個(gè) L型骨牌覆蓋這 3 個(gè)較小的棋盤(pán)的會(huì)合處，從而將原問(wèn)題轉(zhuǎn)化為 4 個(gè)較小規(guī)模的棋盤(pán)覆蓋問(wèn)題。為了在遞歸處理的過(guò)程中使用同一個(gè)棋盤(pán)，將數(shù)組 board 設(shè)為全局變量。
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1