欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【 POJ - 3278】 B - Catch That Cow (BFS)

程序员文章站 2022-07-07 10:37:15
...

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

Hint

The fastest way for Farmer John to reach the fugitive cow is to move along the following path: 5-10-9-18-17, which takes 4 minutes.


思路:

每一步都有三种情况可以选择
x+1 往右一步
x-1 往左一步
x*2 往右x步

通过BFS第一次到达目的位置步数一定是最短的


代码:

#include <iostream>
#include <queue> 
using namespace std;

const int maxn=2e5+50;
int n,k,step[maxn]={0}; //step记录到达位置的最短步数
bool vis[maxn]={false}; //记录是否入过队

int bfs(int u)
{
	queue<int> q;
	step[n]=0;
 	q.push(u);
 	while(!q.empty())
 	{
 		int f=q.front();
 		if(f==k) return step[f];
 		q.pop();
 		if(f+1<maxn && !vis[f+1]) //往右一步
 		{
 			vis[f+1]=1;
 			q.push(f+1);
 			step[f+1]=step[f]+1;
		}
		if(f-1>=0 && !vis[f-1])  //往左一步
		{
			vis[f-1]=1;
			q.push(f-1);
			step[f-1]=step[f]+1;
		}
		if(f*2<maxn && !vis[f*2])  //往右f步
		{
			vis[f*2]=1;
			q.push(f*2);
			step[f*2]=step[f]+1;
		}
	}
	return -1; 
}


int main() 
{
	cin>>n>>k;
	cout<<bfs(n);  
   	return 0;
}

【 POJ - 3278】 B - Catch That Cow (BFS)