Catch That Cow广搜典型例题

比眉伴天荒 2022-05-19 06:29 168阅读 0赞

<table> 
 <tbody> 
 <tr> 
 <td> Problem 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? &nbsp; Input Line 1: Two space-separated integers: N and K &nbsp; Output Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow. &nbsp; Sample Input <pre>
&nbsp;</pre> 5 17 &nbsp; Sample Output <pre>
&nbsp;</pre> 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. </td> 
 </tr> 
 </tbody> 
</table>

/*
 	对于本题，一眼看出用广搜。
 		因为是线性的（没有太多元素），所以不必使用结构体 
 		首先将标志数组初始化为0； 
 		接下来便是构造队列，构造队列的作用是：使多个线索同时前进，符合广搜的要求，
 		也就是说，广搜最核心的东西便是队列的循环；
 		在循环中 ，务必使每一次前进方式都要涉及到，这样才能广搜到最佳路径： 
 		在大部分广搜题中 ，都设置一个结构体，以及结构体类型的队列，在结构体成员中设置要求的结果变量 	
 */ 
 #include<iostream>
 #include<algorithm>
 #include<memory.h>
 #include<cstdio> 
 #include<queue>
 using namespace std;
 const int MAXN=100001;
 const int M=0; 
 int n,k,vis[MAXN];
 void bfs(){
 	queue<int> op; 
 	op.push(n);
 	while(!op.empty()) {
 		int fir=op.front();
 		op.pop(); 
 		if(fir==k) return ; 
 		if(fir+1<MAXN&&!vis[fir+1]) {
 			vis[fir+1]=vis[fir]+1; 
 			op.push(fir+1); 
 		} 
 		if(fir-1>=0&&!vis[fir-1]) {
 			vis[fir-1]=vis[fir]+1; 
 			op.push(fir-1); 
 		} 
 		if(fir*2<MAXN&&!vis[fir*2]) {
 			vis[fir*2]=vis[fir]+1; 
 			op.push(fir*2); 
 		}	
 	} 
 } 
 
 int main()
 {
 
 	while(~scanf("%d%d",&n,&k))
 	{
 		memset(vis,0,sizeof(vis)); 
 		bfs();
 		cout<<vis[k]<<endl; 
 	} 
 	return 0; 
 } 
 //修改了6个小时才AC，水了一逼阿