【题目描述】：农夫约翰被通知，他的一只奶牛逃逸了！所以他决定，马上出发，尽快把那只奶牛抓回来．
他们都站在数轴上．约翰在N处，奶牛在K处．约翰有两种办法移动，步行和瞬移：步行每秒钟可以让约翰从x处走到x+l或x-l处；而瞬移则可让他在1秒内从x处消失，在2x处出现．然而那只逃逸的奶牛，悲剧地没有发现自己的处境多么糟糕，正站在那儿一动不动。
那么，约翰需要多少时间抓住那只牛呢？
【输入描述】：仅有两个整数N和K。
【输出描述】：最短时间
【样例输入】：5 17【样例输出】：4【时间限制、数据范围及描述】：时间：1s 空间：128M
O<=N<=100000
O<=K<=100000
此题是一道标准bfs题目，注意不要越界，还有此点未搜索过即可。
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<cstdlib> #include<cmath> using namespace std; int x,y,a,b; int s[100006]; int q[100006]; int main(){ // freopen("17.in","r",stdin); // freopen("17.out","w",stdout); scanf("%d %d",&a,&b); if(b==0){ cout<<a; return 0; } memset(s,-1,sizeof(s)); int front=0; int rear=0; s[a]=0; q[rear++]=a; while(s[b]==-1 && front!=rear){ x=q[front++]; y=x-1; if(y>0 && y<=100000 && s[y]==-1){ s[y]=s[x]+1; q[rear++]=y; } y=x+1; if(y>0 && y<=100000 && s[y]==-1){ s[y]=s[x]+1; q[rear++]=y; } y=x*2; if(y>0 && y<=100000 && s[y]==-1){ s[y]=s[x]+1; q[rear++]=y; } } cout<<s[b]; return 0; }
转载于:https://www.cnblogs.com/wuhu-JJJ/p/11129370.html
相关资源：DirectX修复工具V4.0增强版