C++算法學(xué)習(xí)之分支限界法的應(yīng)用

第C++算法學(xué)習(xí)之分支限界法的應(yīng)用目錄分支限界1實(shí)驗(yàn)題目：填格子4實(shí)驗(yàn)題目：不如走樓梯分支限界堂練實(shí)驗(yàn)題目：再填格子實(shí)驗(yàn)題目：最短路徑

分支限界1

實(shí)驗(yàn)題目：填格子4

題目描述：

有一個(gè)由數(shù)字0、1組成的方陣中，存在一任意形狀的封閉區(qū)域，封閉區(qū)域由數(shù)字1包圍構(gòu)成，每個(gè)節(jié)點(diǎn)只能走上下左右4個(gè)方向。現(xiàn)要求把封閉區(qū)域內(nèi)的所有空間都填寫成2.例如：66的方陣：

輸入要求：

每組測(cè)試數(shù)據(jù)第一行一個(gè)整數(shù)n(1n30)

接下來(lái)n行，由0和1組成的nn的方陣。

封閉區(qū)域內(nèi)至少有一個(gè)0

實(shí)驗(yàn)代碼及注釋:

#includebits/stdc++.h

usingnamespacestd;

constintM=31;

intMap[M][M];//記錄輸入格子的情況

boolvis[M][M]={false};//標(biāo)記格子訪問(wèn)情況，默認(rèn)未訪問(wèn)

intn;

queueint

voidbfs(intx,inty){//廣度優(yōu)先搜索格子

intdir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};//上下左右四個(gè)方向

vis[x][y]=true;//標(biāo)記格子為訪問(wèn)過(guò)

q.push(x);q.push(y);

while(!q.empty()){

intw=q.front();

q.pop();

inte=q.front();

q.pop();

for(inti=0;ii++){//遍歷四個(gè)方向向外擴(kuò)展一圈

intnow_x=w+dir[i][0];

intnow_y=e+dir[i][1];

//判斷新格子是否合法

if(1=now_xnow_x=n1=now_ynow_y=nMap[now_x][now_y]==0!vis[now_x][now_y]){

vis[now_x][now_y]=true;//標(biāo)記格子為訪問(wèn)過(guò)

q.push(now_x);q.push(now_y);

intmain()

cinn;

for(inti=1;ii++){

for(intj=1;jj++){

cinMap[i][j];

if(Map[i][j]==1)

vis[i][j]=true;

for(inti=1;ii=i+n-1){//從邊緣兩行開始遍歷

for(intj=1;jj++){

if(vis[i][j])

continue;

bfs(i,j);

for(inti=1;ii=i+n-1){//從邊緣兩列開始遍歷

for(intj=1;jj++){

if(vis[j][i])

continue;

bfs(j,i);

for(inti=1;ii++){

for(intj=1;jj++){

if(vis[i][j])//屬于非封閉區(qū)域

coutMap[i][j]"";

else

cout2"";

coutendl;

return0;

算法分析與知識(shí)點(diǎn)：

本題的要求是找出給定方陣中的封閉區(qū)域并將區(qū)域內(nèi)的方格填為2。已知封閉區(qū)域是由一圈完整的1所圍成的，所以只需要遍歷找到1和邊界所圍成的0并加以標(biāo)記，最后只需要將方陣中未標(biāo)記的方格輸出為2就好了。

本題采用廣度優(yōu)先的搜索策略，每次以邊界上的一個(gè)0為廣度優(yōu)先搜索的的起點(diǎn)，可以得知當(dāng)遍歷完邊界上的0所有邊界和1所圍成的區(qū)域就都被標(biāo)記了。

實(shí)驗(yàn)題目：不如走樓梯

題目描述：

有個(gè)電梯，每一層樓都可以停，只是算法混亂了，所以你得寫個(gè)補(bǔ)??；第i層樓(1=i=N)上有一個(gè)數(shù)字Ki(0=Ki=N)，表示上或下的層數(shù)（相對(duì)于當(dāng)前層），每層樓都可以上或下。當(dāng)然，如果不能滿足要求（沒(méi)有的層），相應(yīng)的按鈕就會(huì)失靈。例如：33125代表了Ki（在第一層可以上或下3層；當(dāng)然下是不可能的，第三層可以上或下1層），從一樓開始。在一樓，按上可以到4樓，按下是不起作用的，因?yàn)闆](méi)有-2樓。那么，從A樓到B樓至少要按幾次按鈕？

輸入要求：

共二行。

第一行為3個(gè)用空格隔開的正整數(shù)，表示N,A,B（共基層，開始層，結(jié)束層）；(1N200,1A,BN)N,A,B(1N200,1A,BN)。

第二行為N個(gè)用空格隔開的非負(fù)整數(shù)，表示每層按鈕的數(shù)值Ki。

輸出要求：

一行，即最少按鍵次數(shù)；若無(wú)法到達(dá)，則輸出1。

實(shí)驗(yàn)代碼及注釋:

#includebits/stdc++.h

usingnamespacestd;

intn,a,b,k[210];

boolf[210]={false};//標(biāo)記樓層是否訪問(wèn)過(guò)，默認(rèn)沒(méi)有

voidbfs(){

queuepairint,int//定義隊(duì)列

pairint,intp,t;//當(dāng)前第幾層，當(dāng)前按了幾次

p.first=a;p.second=0;//賦初值

q.push(p);//進(jìn)入隊(duì)列

while(!q.empty()){//隊(duì)列非空

p=q.front();q.pop();

if(f[p.first])//如果樓層訪問(wèn)過(guò)

continue;

f[p.first]=true;//標(biāo)記樓層訪問(wèn)過(guò)

if(p.first==b){//達(dá)到目標(biāo)樓層

coutp.secondendl;

return;//退出搜索

if(p.first-k[p.first]0){//向下按

t.first=p.first-k[p.first];

t.second=p.second+1;

q.push(t);

if(p.first+k[p.first]=n){//向上按

t.first=p.first+k[p.first];

t.second=p.second+1;

q.push(t);

cout-1endl;

intmain(){

cinnab;

for(inti=1;ii++)

cink[i];

bfs();//廣度優(yōu)先搜索答案

return0;

算法分析與知識(shí)點(diǎn)：

本題要求在給定樓層和電梯按鈕分布的前提下給出從初始樓層到目標(biāo)樓層的最小按數(shù)。本題的路徑搜索采用廣度優(yōu)先的搜索策略，只要搜索到目標(biāo)樓層就停止搜索。最小的按電梯按鈕數(shù)為此時(shí)搜索的深度。

分支限界堂練

實(shí)驗(yàn)題目：再填格子

題目描述：

有一個(gè)由數(shù)字0、1組成的方陣中，存在一任意形狀的封閉區(qū)域，封閉區(qū)域由數(shù)字1包圍構(gòu)成，每個(gè)節(jié)點(diǎn)只能走上下左右4個(gè)方向。現(xiàn)要求只把【最大封閉區(qū)域】?jī)?nèi)的空間填寫成2。

輸入要求：

每組測(cè)試數(shù)據(jù)第一行一個(gè)整數(shù)n(1n30)

接下來(lái)n行，由0和1組成的nn的方陣。

封閉區(qū)域內(nèi)至少有一個(gè)0，測(cè)試數(shù)據(jù)保證最大區(qū)域只有一個(gè)。

輸出要求：

已經(jīng)填好數(shù)字2的完整方陣。(每個(gè)數(shù)字后面有一個(gè)空格！）

實(shí)驗(yàn)代碼及注釋:

#includebits/stdc++.h

usingnamespacestd;

inta[35][35]={0};//記錄方陣初始情況

intn;

intdir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};//上下左右四個(gè)方向

intcnt=0;//記錄某一封閉區(qū)域的面積

intcnt_max=0;//記錄最大封閉區(qū)域的面積

intid=3;//搜索標(biāo)記

intid_max=id;//最大封閉區(qū)域?qū)?yīng)的搜索標(biāo)記

voidprit(){//格式化輸出函數(shù)

inti,j;

for(i=1;ii++){

for(j=1;jj++){

if(a[i][j]==1){

couta[i][j]'';

elseif(a[i][j]!=id_max){

cout'0''';

else{

cout'2''';

coutendl;

voiddfs(intx,inty)//將與其鄰接的0坐標(biāo)改為id

inti;

if(a[x][y]!=0||x0||xn+1||y0||yn+1){//檢查是否符合條件

return;

a[x][y]=id;

cnt++;

for(i=0;ii++){//搜索四個(gè)方向

dfs(x+dir[i][0],y+dir[i][1]);

intmain(){

inti,j;

cinn;

for(i=1;ii++){//輸入方陣

for(j=1;jj++){

cina[i][j];

//最外圍的0不形成封閉區(qū)域

dfs(0,0);

id++;

for(i=2;ii++){//從第二層開始形成封閉區(qū)域

for(j=2;jj++){

cnt=0;

dfs(i,j);

if(cntcnt_max){//判斷是否為最大封閉區(qū)域

cnt_max=cnt;

id_max=id;

id++;//搜索標(biāo)記+1

prit();

return0;

算法分析與知識(shí)點(diǎn)：

首先在數(shù)組外面多圍上一圈0，通過(guò)深搜將外層的0及其連接塊染色染色后，剩下的0元素都為封閉區(qū)域，接下來(lái)找到最大的區(qū)域?qū)γ總€(gè)元素都進(jìn)行深搜，找到最大的區(qū)域，記錄其染色編號(hào)。

實(shí)驗(yàn)題目：最短路徑

題目描述：

在下圖中，請(qǐng)使用廣度搜索求出a到b的最短路徑，有色區(qū)域?yàn)椴豢赏ㄟ^(guò)區(qū)域。

輸入要求：

第1行2個(gè)整數(shù)，表示區(qū)域的行數(shù)m和列數(shù)n。1=m,n=20

第2行4個(gè)整數(shù)，表示起點(diǎn)坐標(biāo)和終點(diǎn)坐標(biāo)，坐標(biāo)計(jì)數(shù)從0開始。

第3行開始，m行n列的區(qū)域數(shù)據(jù)，0表示可通行，-1表示不可通行（圖中綠色部分）。

輸出要求：

如圖a的二維信息數(shù)據(jù)，數(shù)值表示步數(shù)。起點(diǎn)終點(diǎn)分別用字符a、b表示。

最后與b同層的點(diǎn)，除了b之外，其他點(diǎn)無(wú)需標(biāo)記。比如sampleout只有b，沒(méi)有9。

每個(gè)數(shù)值靠右占3位輸出（含符號(hào)位），每行最后一個(gè)數(shù)值無(wú)空格換行。

詳見(jiàn)sampleoutput。（如無(wú)路徑，按規(guī)則輸出即可。）

實(shí)驗(yàn)代碼及注釋:

#includebits/stdc++.h

usingnamespacestd;

intMap[21][21]={0};//記錄區(qū)域可通行情況

intm,n;

queueint

intnum=1;//記錄當(dāng)前是第幾輪搜索

voidbfs(intx,inty,intex,intey){

intdir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};//上下左右四個(gè)方向

q.push(x);q.push(y);

while(!q.empty()){

ints=q.size()/2;//當(dāng)前搜索輪次有幾個(gè)點(diǎn)

for(intk=0;kk++){

intcur_x=q.front();

q.pop();

intcur_y=q.front();

q.pop();

for(inti=0;ii++){//遍歷搜索四個(gè)方向

intnow_x=cur_x+dir[i][0];

intnow_y=cur_y+dir[i][1];

if(now_x==exnow_y==ey)//判斷是否到終點(diǎn)

return;

if(0=now_xnow_xn0=now_ynow_ymMap[now_x][now_y]==0){//判斷當(dāng)前點(diǎn)是否符合條件

q.push(now_x);q.push(now_y);

Map[now_x][now_y]=num;//標(biāo)記當(dāng)前點(diǎn)的搜索輪次

num++;

intsx,sy,ex,ey;//起點(diǎn)終點(diǎn)坐標(biāo)

intmain()