BFS問題初探
BFS,BFS，其英文全稱是Breadth First Search,指廣度優先搜索.該類問題利用了STL容器中queue--佇列,進行搜索.原理是在保證當前狀態下,將此狀態入佇列,取出此狀態,佇列消除該狀態,再將該狀態往下一步發展的所有可能入佇列,再將每種可能取出,并且將著它所有可能發展的方向入隊,記錄步數,直到得到目的.
要想學會bfs,必須先了解佇列.我將bfs中可能涉及的佇列的函式列舉出來.
1.創建佇列物件:queue<佇列中元素型別>佇列名(佇列名自己取);(ps:對于元素型別,除了int,char以外,自己定義的型別也可以)
2.隊尾添加元素:佇列名.push(元素名);
3.隊首去除元素:佇列名.pop();
4.訪問隊首:佇列名.front();
5.訪問隊尾:佇列名.back();
6.判斷佇列是否為空:佇列名.empty();
7.回傳佇列大小:佇列名.size();
好了,工欲善其事必先利其器,器已在手,我們就可以初步去了解bfs.
下面是第一個例題.
逃亡的奶牛:農夫約翰已被告知一頭逃亡的奶牛的位置，并希望立即將其抓住， 他從數字線上的點N（0≤N≤100,000）開始，而母牛在同一數字線上的點K（0≤K≤100,000）開始， 農夫約翰有兩種運輸方式：步行和傳送，行走：約翰可以在一分鐘內從任意點X移至點X-1或X + 1.傳送：FJ可以在一分鐘內從任意X點移動到2×X點，如果沒有意識到他的追捕能力的母牛完全沒有動彈，那么農夫約翰要花多長時間才能找回它？
輸入
第1行：兩個以空格分隔的整數：N和K
輸出
第1行：農夫約翰用最少的時間（以分鐘為單位）捉住逃犯，
樣本輸入
5 17
樣本輸出
4
ps:農夫約翰到達逃犯的最快方法是沿著以下路線移動：5-10-9-18-17，這需要4分鐘，
我先把我的代碼放出來,再進行講解:
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int vis[100007];
struct john{
int now,step;//記錄John的位置,步數
};
void bfs(int x,int y){
john bef,nex;
queue<john>qu;
bef.now=x;
bef.step=0;
vis[bef.now]=1;//記錄初始狀態
qu.push(bef);
while(qu.empty()!=1){
bef=qu.front();
qu.pop();
if(bef.now==y){
cout<<bef.step;
return;
}//退出條件
//-------------向前一步
if(vis[bef.now+1]==0&&((bef.now+1)<=100000)){
nex.now=bef.now+1;
nex.step=bef.step+1;
vis[nex.now]=1;
qu.push(nex);
}
//-------------向后一步
if(vis[bef.now-1]==0&&((bef.now-1)>=0)){
nex.now=bef.now-1;
nex.step=bef.step+1;
vis[nex.now]=1;
qu.push(nex);
}
//-------------特殊
if(vis[2*bef.now]==0&&((bef.now*2)>=0)){
nex.now=bef.now*2;
nex.step=bef.step+1;
vis[nex.now]=1;
qu.push(nex);
}
}
cout<<"-1";
}
int main(){
int john,cow;
memset(vis,0,sizeof(vis));
cin>>john>>cow;
bfs(john,cow);
}
然后是問題分析:
入題目所示,農夫有兩種運動方式,最多有三種運動所的結果,為什么是最多呢,因為當約翰在0或者N位置的時候,分別不能往后,往前走,這也是要考慮的條件之一.理解題目所給的追捕方式,無非就是往前一步,往后一步,瞬移到兩倍下標的位置(例如從3直接到6,從2直接到4).了解此問題后,我們直接敲代碼.
首先就是初始處理,關于如何儲存農夫此時的狀態和步數,struct結構體似乎是一個不錯的選擇:
struct john{
int now;//記錄此時狀態,在某個點
int step;//記錄從初始位置John走了多少步
};當然,還有一個問題我沒有提及,就是對于bfs重復的處理,如果john沒睡醒,兩次到達了點5,那是不是其實第二次是完全沒有必要的呢?對,進行第二次的話毫無意義,因為我已經到過該點,后續操作將與第一次完全重合,浪費空間時間,此時我們可以引入一個標記陣列.
int vis[100007];標記陣列的大小依照題目來看,型別也可以是bool型,只要能達到它的作用,標記john已經到達的位置即可,我們可以設john沒到過的地方為0,當要進行下一步操作時,我們可以判斷,如果vis[下一步到達的地點下標]==0,那么就可以到達此處,并且將該種情況入隊記錄后,將vis[該點下標]更新為1,那么下次到達該點也就不會進行入隊操作.
然后就是進行對john初始狀態的處理,直接用一個結構體將其初始狀態記錄:
john bef;//此處定義同型別結構體
queue<john>qu;//創建佇列
bef.n=x;//將john一開始的位置記錄在結構體里面
bef.step=0;//此時john還沒有動
vis[bef.n]=1;//記錄john已經到過該點記錄完初始狀態,就把他入隊.在進入一個while回圈.該回圈為while(qu.empty()!=1).進入這樣一個回圈是為什么呢?因為我們在此回圈中會將每一種可能進行搜索,如果不符合情況就不會入隊,回圈往復,當搜索多次遇見不能夠入隊的情況,可能是所有的下一步都已經被標記,而qu佇列又需要出隊元素,當佇列為空時,也就說明沒有往下一步的可能了,但是仍然沒有達到目標地,這就是無法到達的情況,當while回圈到佇列空了,還未到達,可以按題意輸出NO了.
然后就是退出條件,也就是滿足了題目條件,我們可以取出隊首元素直接與目的地對比,如果相等直接輸出步數,return.
if(bef.now==y){
cout<<bef.step;
return;
}//退出條件最后需要講解的就是對于每次到達一個點后,他下一步可能到達的地點.
//向前
if(vis[bef.now+1]==0&&((bef.now+1)<=100000)){
nex.now=bef.now+1;
nex.step=bef.step+1;
vis[nex.now]=1;
qu.push(nex);
}
//-------------向后一步
if(vis[bef.now-1]==0&&((bef.now-1)>=0)){
nex.now=bef.now-1;
nex.step=bef.step+1;
vis[nex.now]=1;
qu.push(nex);
}
//-------------特殊
if(vis[2*bef.now]==0&&((bef.now*2)>=0)){
nex.now=bef.now*2;
nex.step=bef.step+1;
vis[nex.now]=1;
qu.push(nex);
} 可以看到,每次我都進行了vis的判斷,如果沒到過,并且沒有到邊界,我就會進行入隊操作,這里的到邊界,以后很多題會出現,而且更加復雜,這里僅僅要注意在0位置不能往前走,在
N位置不能往后走,這種情況也要重點注意哦.對于后續可能情況處理,我引入了新的結構體變數,nex,他的好處就是我可以保留上一步,也就是bef的狀態,將下一步進行操作(位置的改變,步數的增加,標記點).
這是一個挺簡單的bfs了,bfs的模板基本如此,記錄初始狀態,while回圈,,回圈中退出條件,不能退出就往下一步搜索.其實bfs難點還是在于邊界判斷,標記,往下一步搜索下一步所有的可能性.
下面我再舉兩個題,針對它們的標記和退出條件講解.(畢竟bfs基礎題的話樣子都差不多,不同的就是1退出條件和下一步分支,標記等).
問題描述
有一個奇怪的升降機，升降機可以根據需要停在每個樓層，每個樓層上都有一個數字Ki（0 <= Ki <= N），該升降機只有兩個按鈕：上和下， 在第i層，如果您按“ UP”按鈕，您將在Ki層上，即，您將進入第i + Ki層，同樣，如果您按“ DOWN”按鈕，則將在下層 Ki樓層，即您將進入i-Ki樓層， 當然，電梯不能高于N，不能低于1，例如，有一個5層樓的建筑物，k1 = 3，k2 = 3，k3 = 1，k4 = 2，k5 =5，從1樓開始，您可以按“ UP”按鈕，然后您將上升到4樓，如果您按“ DOWN”按鈕，則電梯不能 它，因為它不能下降到-2樓，如您所知，-2樓不存在，
問題來了：當您在A樓上并且想去B樓時，他至少必須按“上”或“下”按鈕多少次？
輸入
輸入包含多個測驗用例，每個測驗用例包含兩行，
第一行包含上述三個整數N，A，B（1 <= N，A，B <= 200），第二行包含N個整數k1，k2，.... kn，
單個0表示輸入的結尾，
輸出
對于每種輸入輸出情況，整數時，在A樓時必須最少按下一次按鈕，然后才想轉到B樓，如果無法到達B樓，則列印“ -1”，
樣本輸入
5 1 5
3 3 1 2 5
0
樣本輸出
3
本題也是基礎的bfs,可以把上題搞明白后依葫蘆畫瓢,套用模板,注意退出條件,分支可能,標記即可.先上代碼:
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int flo[201];//記錄該層可以操作的層數
int vis[201];//標記是否已經到達
struct floor{
int now;//現在所處狀態
int step;//步數
};
void bfs(int N,int A,int B){
queue<floor>qu;
floor bef,nex;
bef.now=A;
bef.step=0;
vis[A]==1;//記錄初始狀態
qu.push(bef);
while(qu.empty()==0){
bef=qu.front();
qu.pop();
if(bef.now==B){
printf("%d\n",bef.step);
return;
}//退出條件
else{
nex.now=bef.now+flo[bef.now];
if(nex.now<=N&&vis[nex.now]!=1){
nex.step=bef.step+1;
vis[nex.now]=1;
qu.push(nex);
}//往上走
nex.now=bef.now-flo[bef.now];
if(nex.now>=1&&vis[nex.now]!=1){
nex.step=bef.step+1;
vis[nex.now]=1;
qu.push(nex);
}//往下走
}
}
printf("-1\n");//結果不存在
return;
}
int main(){
int N,A,B;//N為共有多少層,A起始,B結尾
while(scanf("%d",&N)&&N!=0){
scanf("%d%d",&A,&B);
memset(vis,0,sizeof(vis));//初始化標記陣列
for(int i=1;i<=N;i++){
scanf("%d",&flo[i]);//記錄每一層可以上下的層數
}
bfs(N,A,B);
}
}該題有一個陣列,用來存樓層上可運算元,我之前提到過可以套模板,但是切忌生搬硬套,仔細審題后,將題目任務拆分逐步實作,不能漏下一個,這也是我寫代碼的思想.
針對該題與上題有一個點要注意一下,多組資料的讀入,如果粗心會發生一個問題,忘記將vis陣列初始化而對下一組資料進行搜索,這樣很可能導致可以到達目的地的代碼無法搜索到最后,因為你上一組的標記沒洗掉,令這組本該到達的地方沒有到達,一定要注意,細節決定成敗,bfs代碼初學可能較長,不注重細節幾百行debug到頭顱爆炸.
memset(vis,0,sizeof(vis));//初始化標記陣列
//每次回圈都要初始化注意本題也有邊界,需要判斷下一步到達的樓層到底存不存在.
然后就是最后一個題:
Problem Description
大家一定覺的運動以后喝可樂是一件很愜意的事情，但是seeyou卻不這么認為，因為每次當seeyou買了可樂以后，阿牛就要求和seeyou一起分享這一瓶可樂，而且一定要喝的和seeyou一樣多，但seeyou的手中只有兩個杯子，它們的容量分別是N 毫升和M 毫升 可樂的體積為S （S<101）毫升 (正好裝滿一瓶) ，它們三個之間可以相互倒可樂 (都是沒有刻度的，且 S==N+M，101＞S＞0，N＞0，M＞0) ，聰明的ACMER你們說他們能平分嗎？如果能請輸出倒可樂的最少的次數，如果不能輸出"NO"，
Input
三個整數 : S 可樂的體積 , N 和 M是兩個杯子的容量，以"0 0 0"結束，
Output
如果能平分的話請輸出最少要倒的次數，否則輸出"NO"，
Sample Input
7 4 3
4 1 3
0 0 0
Sample Output
NO
3
該題比較麻煩的就是每次倒可樂后下一種可能的分支,可能有六種,s->n,s->m,n->s,n->m,m->s,m->n.每一種情況都不能漏,目前有兩個思路,1.直接將每種情況列舉,2.建立兩個小陣列,分別將每次的s,m,n中可樂可能情況存入,再使用for回圈倒水(此代碼我的學長已經實作,我還沒寫出來).我采用的第一種方法.第二個難點就是標記,三個容器如何標記?因為本題資料不算太大,我采用了三維陣列vis[101][101][101],陣列長度沒有超過1e8.代碼呈現如下:
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int vis[101][101][101];//標記狀態
struct kola{
int s;
int n;
int m;//s,n,m中可樂量
int step;//步數
};
bool che(kola bef){
if((bef.m==bef.n)&&bef.s==0)return false;
else if((bef.m==bef.s)&&bef.n==0)return false;
else if((bef.s==bef.n)&&bef.m==0)return false;
else return true;
}//退出條件封裝函式,當三者之中一個空,兩個相等,即可停止搜索.
void bfs(int S,int N,int M){
int a,b,c;
memset(vis,0,sizeof(vis));
queue<kola>qu;
kola bef,nex;
bef.s=S;
bef.m=0;
bef.n=0;
bef.step=0;
vis[bef.s][bef.n][bef.m]=1;//記錄初始狀態
qu.push(bef);
while(qu.empty()!=1){
bef=qu.front();
qu.pop();
a=bef.s;
b=bef.n;
c=bef.m;//abc比較短,方便記錄,平時不建議寫這種變數名,變數名一多容易搞混
if(che(bef)==false){
printf("%d\n",bef.step);
return;
}
//--從S倒---------------------------------------------//
if(N-b>=a&&vis[0][a+b][c]==0){
qu.push({0,a+b,c,bef.step+1});
vis[0][a+b][c]=1;
} //可以將s全部倒進n
else if(N-b<a&&vis[a-(N-b)][N][c]==0){
qu.push({a-(N-b),N,c,bef.step+1});
vis[a-(N-b)][N][c]=1; //不可以將s全部倒進n
}//-------------------------------s向n倒水
if(M-c>=a&&vis[0][b][a+c]==0){
qu.push({0,b,a+c,bef.step+1});
vis[0][b][a+c]=1;
} //可以將s全部倒進m
else if(M-c<a&&vis[a-(M-c)][b][M]==0){
qu.push({a-(M-c),b,M,bef.step+1});
vis[a-(M-c)][b][M]=1; //不可以將s全部倒進n(ps:下面兩段與上面幾乎相同)
}//--------------------------------s向m倒水
//--從N倒----------------------------------------------//
if(S-a>=b&&vis[a+b][0][c]==0){
qu.push({a+b,0,c,bef.step+1});
vis[a+b][0][c]=1;
}
else if(S-a<b&&vis[S][b-(S-a)][c]==0){
qu.push({S,b-(S-a),c,bef.step+1});
vis[S][b-(S-a)][c]=1;
}//--------------------------------n向s倒水
if(M-c>=b&&vis[a][0][b+c]==0){
qu.push({a,0,b+c,bef.step+1});
vis[a][0][b+c]=1;
}
else if(M-c<b&&vis[a][b-(M-c)][M]==0){
qu.push({a,b-(M-c),M,bef.step+1});
vis[a][b-(M-c)][M]=1;
}//--------------------------------n向m倒水
//--從M倒---------------------------------------------//
if(S-a>=c&&vis[a+c][b][0]==0){
qu.push({a+c,b,0,bef.step+1});
vis[a+c][b][0]=1;
}
else if(S-a<c&&vis[S][b][c-(S-a)]==0){
qu.push({S,b,c-(S-a),bef.step+1});
vis[S][b][c-(S-a)]=1;
}//---------------------------------m向s倒水
if(N-b>=c&&vis[a][b+c][0]==0){
qu.push({a,b+c,0,bef.step+1});
vis[a][b+c][0]=1;
}
else if(N-b<c&&vis[a][N][c-(N-b)]==0){
qu.push({a,N,c-(N-b),bef.step+1});
vis[a][N][c-(N-b)]=1;
}//--------------------------------m向n倒水
//-------------------------------------------------//
}
printf("NO\n");
return;//沒有可能相等
}
int main(){
int S,N,M;
while(scanf("%d%d%d",&S,&N,&M)&&N!=0){
bfs(S,N,M);
}
}當把s向n,m倒可樂寫出來了,可以直接復制粘貼然后改資料寫出所有情況.(類比)
bfs比較注重于考驗細心(個人觀點),你要考慮到是否有邊界,如何標記,一共有多少種情況......當然,在完成基本代碼后可以進行優化,就像剛才倒可樂的題目,第二種思想大家也可以思考一下.
我也是個初學者,這是第一次寫博客,下次會嘗試寫一下dfs,有什么不足希望大家指出來.qwq
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/282652.html
標籤：其他