棋盤(pán)覆蓋問(wèn)題

問(wèn)題說(shuō)明

在一個(gè)2^k * 2^k個(gè)方格組成的棋盤(pán)中，恰有一個(gè)方格與其它方格不同，稱(chēng)該方格為一特殊方格。

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

功能說(shuō)明

本程序用分治法的思想解決了棋盤(pán)覆蓋問(wèn)題，顯示輸出

代碼簡(jiǎn)述

用戶(hù)輸入數(shù)據(jù)，程序輸入檢測(cè)，動(dòng)態(tài)分配空間，調(diào)用棋盤(pán)覆蓋函數(shù)，把計(jì)算結(jié)果存儲(chǔ)到board（二維數(shù)組指針），顯示輸出。

其中棋盤(pán)覆蓋函數(shù)用分治的思想把棋盤(pán)分成四份，遞歸求解。

源碼示例：

#include《iostream》#include《math.h》#include《cctype》usingnamespacestd;intnum_Now =0;//記錄L型骨牌編號(hào)int**board =NULL;//棋盤(pán)指針//函數(shù)聲明

voidChessBoard（intnum_BoardTopLeftRow，intnum_BoardTopLeftColumn，intnum_SpecialRow，intnum_SpecialColumn，intboardSize）;intmain（） {intnum_BoardTopLeftRow =0，//棋盤(pán)左上角的行號(hào)

num_BoardTopLeftColumn =0，//棋盤(pán)左上角的列號(hào)num_SpecialRow =0，//特殊方格所在的行號(hào)num_SpecialColumn =0，//特殊方格所在的列號(hào)boardSize =0，//棋盤(pán)大小k =0;//構(gòu)成的（2^k）*（2^k）個(gè)方格的棋盤(pán)

//用戶(hù)界面cout 《《“---------------- 棋盤(pán)覆蓋問(wèn)題 ----------------”《《 endl;cout 《《“請(qǐng)輸入k（k》=0），構(gòu)成（2^k）*（2^k）個(gè)方格的棋盤(pán)”《《 endl;//輸入k值cin 》》 k;//判斷輸入數(shù)據(jù)合法性，包括檢查輸入是否為數(shù)字，k值是否大于0if（cin.fail（） || k 《0）{cout 《《“輸入k錯(cuò)誤！”《《 endl;system（“pause”）;

return0;}//計(jì)算棋盤(pán)大小

boardSize =pow（2， k）;cout 《《“請(qǐng)輸入特殊方格所在的行號(hào)和列號(hào)（從0開(kāi)始，用空格隔開(kāi)）”《《 endl;//輸入特殊方格所在的行號(hào)和列號(hào)cin 》》 num_SpecialRow 》》 num_SpecialColumn;//判斷輸入數(shù)據(jù)合法性，包括檢查輸入是否為數(shù)字，特殊方格行號(hào)列號(hào)是否大于0，特殊方格行號(hào)列號(hào)是否不大于棋盤(pán)大小

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

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

0board［num_SpecialRow］［num_SpecialColumn］ =0;//執(zhí)行棋盤(pán)覆蓋函數(shù)

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;//暫停查看結(jié)果

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

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

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

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

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

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

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

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

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

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

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

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

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

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

board［num_BoardTopLeftRow + size］［num_BoardTopLeftColumn + size］ = num;//遞歸覆蓋其余棋盤(pán)

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

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

責(zé)任編輯：haq