本文主要是介绍POJ3278 Catch That Cow(最短路+bfs)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Description
Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 ≤ N ≤ 100,000) on a number line and the cow is at a point K (0 ≤ K ≤ 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting.
* Walking: FJ can move from any point X to the points X - 1 or X + 1 in a single minute
* Teleporting: FJ can move from any point X to the point 2 × X in a single minute.
If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?
Input
Line 1: Two space-separated integers: N and K
Output
Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.
Sample Input
5 17
Sample Output
4
大致题意，牛的起始坐标为n，在每一时刻都可以转移到n-1, n+1， 2*n的位置，问你到达K时最少要多少步；
这一题一想其实跟迷宫求最短路径是一模一样的。由于场景变了，坐标移动方式变了，差点没反应过来，不懂的建议要把迷宫求最短路搞懂；
另外这题直接就是套用bfs的一般写法，visit数组表示是否已经被访问过，d数组表示到起始点的距离，在这边是表示移动了多少次。代码不长也不难
AC代码：
# include <stdio.h>
# include <queue>
# include <string.h>
using namespace std;
int visit[100010];
int d[100010];
queue<int> q;
int main(){int i, j, n, k, next, now;while(scanf("%d%d", &n, &k)!=EOF){memset(d, 0, sizeof(d));memset(visit, 0, sizeof(visit));while(!q.empty()){q.pop();}q.push(n);if(n==k){printf("0\n");continue;}int flage=0;while(!q.empty()){now=q.front();q.pop();for(i=1; i<=3; i++){if(i==1){next=now+1;}else if(i==2){next=now-1;}else{next=now*2;}if(next<0||next>100000){continue;}if(!visit[next]){q.push(next);visit[next]=1;d[next]=d[now]+1;}if(next==k){printf("%d\n", d[next]);flage=1;break;}}if(flage){break;}}}return 0;
}
这篇关于POJ3278 Catch That Cow(最短路+bfs)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
