C++中棋盤覆蓋問題分析

棋盤覆蓋問題

問題說明

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

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

功能說明

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

代碼簡述

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

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

源碼示例：

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

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

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

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

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

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

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;}//分配棋盤空間

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

0board［num_SpecialRow］［num_SpecialColumn］ =0;//執(zhí)行棋盤覆蓋函數(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;}//棋盤覆蓋函數(shù)

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

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{//用編號(hào)為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{//用編號(hào)為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{//用編號(hào)為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{//用編號(hào)為num的L型骨牌覆蓋左上角

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

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

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

責(zé)任編輯：haq