題目：

農(nóng)夫知道一頭牛的位置，想要抓住它。農(nóng)夫和牛都于數(shù)軸上 ，農(nóng)夫起始位于點 N(0<=N<=100000) ，牛位于點 K(0<=K<=100000) 。農(nóng)夫有兩種移動方式： 1、從 X移動到 X-1或X+1 ，每次移動花費一分鐘 2、從 X移動到 2*X ，每次移動花費一分鐘 假設(shè)牛沒有意識到農(nóng)夫的行動，站在原地不。最少要花多少時間才能抓住牛？
Input
一行: 以空格分隔的兩個字母: N 和 K
Output
一行: 農(nóng)夫抓住牛需要的最少時間，單位分鐘
Sample Input
5 17
Sample Output
4
Hint
農(nóng)夫使用最短時間抓住牛的方案如下: 5-10-9-18-17, 需要4分鐘.

分析與解答

由于無法確定深度，因此用bfs廣搜，bfs不需要回溯，是一層一層推進(jìn)，一直到最后的解

這題有三種情況，后退一步，前進(jìn)一步，前進(jìn)二倍當(dāng)前距離，那我們就層次遍歷，每層輸入到隊列里，輸完了就把上一層pop掉，就是不斷遍歷并且查找，遇到最終結(jié)果return并輸出time即可
為了減小時間，我們需要判重，每次只入那些曾經(jīng)沒出現(xiàn)過的數(shù)。
這一類bfs具體怎么實現(xiàn)，就是先建一個隊列，然后把第一個數(shù)push里面，只要隊列不空，就一直對隊列進(jìn)行出隊入隊操作。需要有兩個變量 m,next;m存的是根結(jié)點，每次循環(huán)最初需要把他取出，next存的是由根結(jié)點+1-1*2從而形成的子結(jié)點，我們存子結(jié)點時注意判重，不重復(fù)我們就push next，并且標(biāo)記。注意每次操作完之后我們都要檢查一下是不是滿足最終的結(jié)果，如果滿足我們直接return就行

代碼參考：https://blog.csdn.net/qq_38620461/article/details/78445374

#include<bits/stdc++.h> using namespace std; int to[2]={1,-1}; int a,b,sum; int vis[100000]; struct place {int x,time; }; int check(place k) {if(k.x<0||k.x>100000||vis[k.x]==1)return 0;return 1; } int bfs(place n) {place m,next;queue<place>w;w.push(n);while(!w.empty()) {m=w.front();w.pop();if(m.x==b)return m.time;for(int i=0;i<2;i++){next.x=m.x+to[i];next.time=m.time+1;if(next.x==b)return next.time;if(check(next)){w.push(next);vis[next.x]=1;}}next.x=m.x*2;next.time=m.time+1;if(next.x==b)return next.time;if(check(next)){w.push(next);vis[next.x]=1;}}return 0; } int main() {int i,j,t;place x1;while(~scanf("%d %d",&a,&b)){memset(vis,0,sizeof(vis));x1.x=a;x1.time=0;vis[x1.x]=1;sum=0;sum=bfs(x1);printf("%d\n",sum);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的（BFS）Catch That Cow（poj3278）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。