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