題目鏈接：戳此進入

這道題如果用DFS就是一路走到頭沒法向回拐，所以不能用DFS，我們用BFS+隊列，廣搜一下，

第一先確定人的位置，之后確定牛的位置，如果人在牛前，人就只能后退，那差幾步就是幾分鐘。

第二種是牛在人前面，然后人開始找牛，三種方法，步數+1，步數-1，步數*2，

然后開始遍歷，先把人開始的位置壓入隊列，遍歷下面3個地方，判斷是否找到，判斷是否越界，然后把隊列頭依次拿出，每次拿出都會往下遍歷3種情況，步數+1，步數-1，步數*2，如果有點遍歷過了，就不再遍歷，每次遍歷同時更新步數，

下面是實現代碼

#include<iostream> #include<queue> #include<cstring> #include<cstdio> #include <algorithm> using namespace std;queue<int> q; int m,n; int step[100010]; int vis[100010]; int rear,front;//rear表示下一步 int BFS(){int i;q.push(n);//把農民的位置壓入隊列 step[n]=0;//步數記為0 vis[n]=1;標記這個點走過 while(!q.empty()){//隊列不為空哦時執行 front=q.front();//最開始的位置 q.pop();//彈出隊列頭 for(i=0;i<3;i++)//三種走法，三種循環 {if(i==0)rear=front+1;//第一種下一步+1 if(i==1)rear=front-1;//第二種下一步-1 if(i==2)rear=front*2;//第三種步數翻倍 if(rear>=0&&rear<=100000&&vis[rear]==0)//判斷是否越界，并且這一步沒有走過 {vis[rear]=1;//標記這一步走過了 step[rear]=step[front]+1;// 步數+1 q.push(rear);//將當前位置壓入隊列 }if(rear==m)return step[rear];}}return -1;}int main(){cin>>n>>m;memset(step,0,sizeof(step));//初始化為0 memset(vis,0,sizeof(vis));//初始化為falsecout<<BFS();return 0; }

第二種方法是定義一個結構體

#include<iostream> #include<cstdio> #include<algorithm> #include<queue> #include<cstring> using namespace std; struct node {int x;int c; } pos[200000]; int n,k; queue<node> q; bool vis[200000];//為什么設置成200000呢？因為p*2的時候就越界了雖然不做判斷，但是需要這個范圍，如果沒有程序會跑崩潰 int bfs() {int p,cnt;while(!q.empty()){p=q.front().x;//記錄位置 cnt=q.front().c;//記錄步數 q.pop();//取出隊列第一個 if(p==k) return cnt;//如果找到牛就返回了 if(!vis[p-1]&&p>0)//能夠退一步 {vis[p-1]=1;pos[p-1].c=cnt+1;pos[p-1].x=p-1;q.push(pos[p-1]);}if(p<k)//如果人再牛后面 {if(!vis[p+1])//能夠前進一步 {vis[p+1]=1;pos[p+1].c=cnt+1;pos[p+1].x=p+1;q.push(pos[p+1]);}if(!vis[2*p]){vis[2*p]=1;pos[2*p].c=cnt+1;pos[2*p].x=p*2;q.push(pos[2*p]);}}} } int main(){cin>>n>>k;memset(vis,0,sizeof(vis));//初始化 memset(pos,0,sizeof(pos));//初始化 vis[n]=1;//標記這個位置已經搜索過了 pos[n].x=n;//給結構體賦值（位置） pos[n].c=0;//給結構體賦值 （步數） q.push(pos[n]);//把第一個結構體拉入列隊 cout<<bfs()<<endl;;return 0; }

?

#include<iostream> #include<cstring> #include<stdio.h> #include<math.h> #include<queue> #include<vector> #include<map> #include<set> #include<stack> #include<algorithm> using namespace std; typedef long long LL; const int maxn = 100010; int x, y; int ans = 0;bool inq[maxn]; struct node{int x;int step;node(){step = 0;} };bool check(node now){if(now.x < 0 || now.x > 100010){return 0;}return 1; } int BFS(node now){queue<node> q;q.push(now);inq[now.x] = 1;while(!q.empty()){node front = q.front();if(front.x == y){return front.step;}q.pop();node next;for(int i = 1; i <= 3;i ++){if(i == 1)next.x = front.x + 1;else if(i == 2)next.x = front.x - 1; else next.x = front.x * 2;if(check(next) && !inq[next.x]){inq[next.x] = 1;next.step = front.step + 1;q.push(next);}} }return 0; }int main(){scanf("%d%d", &x, &y) ;node start;start.x = x;int ans;ans = BFS(start);printf("%d\n", ans);return 0; }

?

總結

以上是生活随笔為你收集整理的POJ 3278，抓牛问题（BFS）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。