棋盤覆蓋問題

問題說明

在一個2^k * 2^k個方格組成的棋盤中，恰有一個方格與其它方格不同，稱該方格為一特殊方格。

棋盤覆蓋問題就是要用圖示的4種不同形態的L型骨牌覆蓋給定棋盤上除特殊方格之外的所有方格，且任何2個L型骨牌不得重疊覆蓋。

功能說明

本程序用分治法的思想解決了棋盤覆蓋問題，顯示輸出

代碼簡述

用戶輸入數據，程序輸入檢測，動態分配空間，調用棋盤覆蓋函數，把計算結果存儲到board（二維數組指針），顯示輸出。

其中棋盤覆蓋函數用分治的思想把棋盤分成四份，遞歸求解。

源碼示例：

#include《iostream》#include《math.h》#include《cctype》usingnamespacestd;intnum_Now =0;//記錄L型骨牌編號int**board =NULL;//棋盤指針//函數聲明

voidChessBoard（intnum_BoardTopLeftRow，intnum_BoardTopLeftColumn，intnum_SpecialRow，intnum_SpecialColumn，intboardSize）;intmain（） {intnum_BoardTopLeftRow =0，//棋盤左上角的行號

num_BoardTopLeftColumn =0，//棋盤左上角的列號num_SpecialRow =0，//特殊方格所在的行號num_SpecialColumn =0，//特殊方格所在的列號boardSize =0，//棋盤大小k =0;//構成的（2^k）*（2^k）個方格的棋盤

//用戶界面cout 《《“---------------- 棋盤覆蓋問題 ----------------”《《 endl;cout 《《“請輸入k（k》=0），構成（2^k）*（2^k）個方格的棋盤”《《 endl;//輸入k值cin 》》 k;//判斷輸入數據合法性，包括檢查輸入是否為數字，k值是否大于0if（cin.fail（） || k 《0）{cout 《《“輸入k錯誤！”《《 endl;system（“pause”）;

return0;}//計算棋盤大小

boardSize =pow（2， k）;cout 《《“請輸入特殊方格所在的行號和列號（從0開始，用空格隔開）”《《 endl;//輸入特殊方格所在的行號和列號cin 》》 num_SpecialRow 》》 num_SpecialColumn;//判斷輸入數據合法性，包括檢查輸入是否為數字，特殊方格行號列號是否大于0，特殊方格行號列號是否不大于棋盤大小

if（cin.fail（） || num_SpecialRow 《0|| num_SpecialColumn 《0|| num_SpecialRow 》= boardSize || num_SpecialColumn 》= boardSize）{cout 《《“輸入行號或列號錯誤！”《《 endl;system（“pause”）;return0;}//分配棋盤空間

board =newint*［boardSize］;for（autoi =0; i 《 boardSize; i++）{board［i］ =newint［boardSize］;}//為特殊方格賦初值

0board［num_SpecialRow］［num_SpecialColumn］ =0;//執行棋盤覆蓋函數

ChessBoard（num_BoardTopLeftRow， num_BoardTopLeftColumn， num_SpecialRow， num_SpecialColumn， boardSize）;//顯示輸出

cout 《《“------------------------------------------------”《《 endl;for（autoi =0; i 《 boardSize; i++）{for（autoj =0; j 《 boardSize; j++）{cout 《《 board［i］［j］ 《《“ ”;}cout 《《 endl;}cout 《《“------------------------------------------------”《《 endl;//暫停查看結果

system（“pause”）;//釋放內存for（inti =0; i 《= boardSize; i++）delete［］board［i］;delete［］board;//指針置空board =NULL;return0;}//棋盤覆蓋函數

voidChessBoard（intnum_BoardTopLeftRow，intnum_BoardTopLeftColumn，intnum_SpecialRow，intnum_SpecialColumn，intboardSize）{//棋盤大小為1則直接返回if（boardSize ==1）return;intnum = ++num_Now，//L型骨牌編號

size = boardSize /2;//分割棋盤，行列各一分為二//覆蓋左上角子棋盤

if（num_SpecialRow 《 num_BoardTopLeftRow + size && num_SpecialColumn 《 num_BoardTopLeftColumn + size）{//遞歸覆蓋含有特殊方格的子棋盤

ChessBoard（num_BoardTopLeftRow， num_BoardTopLeftColumn， num_SpecialRow， num_SpecialColumn， size）;}else{//用編號為num的L型骨牌覆蓋右下角

board［num_BoardTopLeftRow + size -1］［num_BoardTopLeftColumn + size -1］ = num;//遞歸覆蓋其余棋盤

ChessBoard（num_BoardTopLeftRow， num_BoardTopLeftColumn， num_BoardTopLeftRow + size -1， num_BoardTopLeftColumn + size -1， size）;}//覆蓋右上角子棋盤

if（num_SpecialRow 《 num_BoardTopLeftRow + size && num_SpecialColumn 》= num_BoardTopLeftColumn + size）{//遞歸覆蓋含有特殊方格的子棋盤ChessBoard（num_BoardTopLeftRow， num_BoardTopLeftColumn + size， num_SpecialRow， num_SpecialColumn， size）;}else{//用編號為num的L型骨牌覆蓋左下角

board［num_BoardTopLeftRow + size -1］［num_BoardTopLeftColumn + size］ = num;//遞歸覆蓋其余棋盤ChessBoard（num_BoardTopLeftRow， num_BoardTopLeftColumn + size， num_BoardTopLeftRow + size -1， num_BoardTopLeftColumn + size， size）;}//覆蓋左下角子棋盤

if（num_SpecialRow 》= num_BoardTopLeftRow + size && num_SpecialColumn 《 num_BoardTopLeftColumn + size）{//遞歸覆蓋含有特殊方格的子棋盤ChessBoard（num_BoardTopLeftRow + size， num_BoardTopLeftColumn， num_SpecialRow， num_SpecialColumn， size）;}else{//用編號為num的L型骨牌覆蓋右上角

board［num_BoardTopLeftRow + size］［num_BoardTopLeftColumn + size -1］ = num;//遞歸覆蓋其余棋盤

ChessBoard（num_BoardTopLeftRow + size， num_BoardTopLeftColumn， num_BoardTopLeftRow + size， num_BoardTopLeftColumn + size -1， size）;}//覆蓋右下角子棋盤

if（num_SpecialRow 》= num_BoardTopLeftRow + size && num_SpecialColumn 》= num_BoardTopLeftColumn + size）{//遞歸覆蓋含有特殊方格的子棋盤

ChessBoard（num_BoardTopLeftRow + size， num_BoardTopLeftColumn + size， num_SpecialRow， num_SpecialColumn， size）;}else{//用編號為num的L型骨牌覆蓋左上角

board［num_BoardTopLeftRow + size］［num_BoardTopLeftColumn + size］ = num;//遞歸覆蓋其余棋盤

ChessBoard（num_BoardTopLeftRow + size， num_BoardTopLeftColumn + size， num_BoardTopLeftRow + size， num_BoardTopLeftColumn + size， size）;}}

今天的分享就到這里了，大家要好好學C++喲~

責任編輯：haq