题目描述
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?
题目描述
每次牛都可以在数轴上移动，每次+1或者-1，或者是坐标*2，求最少的步数。
解法
非常非常非常地容易就可以知道这道题肯定是宽搜宽搜宽搜LJ附身，那么我们按照bfs一步一步来就可以了。
虽然有一些比较杂的优化，但是大体不变就可以A掉了。
ac代码
#include<cstdio>
#include<queue>
#include<cstring>
#include<iostream>
#define N 200005
using namespace std;
struct node{int x,st;};
bool vis[N];
queue<node>q;
int main(){
int x,y;
while(~scanf("%d%d",&x,&y)){
while(!q.empty())q.pop();
memset(vis,false,sizeof(vis)); vis[x]=true;
q.push((node){x,0});
while(!q.empty()){
node u=q.front(); q.pop();
if(u.x==y){printf("%d\n",u.st);break;}
int ste=u.st+1;
if(u.x+1<=100000&&!vis[u.x+1])q.push((node){u.x+1,ste}),vis[u.x+1]=true;
if(u.x-1>=0&&!vis[u.x-1])q.push((node){u.x-1,ste}),vis[u.x-1]=true;
if(u.x*2<=100000&&!vis[u.x*2])q.push((node){u.x*2,ste}),vis[u.x*2]=true;
}
}
return 0;
}