杭电 2717 Catch That Cow

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?   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 题意：输入两个数a,b只能进行+1，-1，*2三种运算从a得到b最少的步数 使用队列， #include<iostream> #include<stdio.h> #include<string> #include<cstring> #include<math.h> #include<queue> using namespace std; int N=1000000; int a[1010000]={0};防止走重，即第一步走过了后面不应该再走一次 struct ft//结构体，包含数和步数 {     int x,y; }p; int k; int bfs(int n) {     queue<ft>Q;//建队     p.x=n,p.y=0;     a[n]=1;     Q.push(p);入队     ft cur, nex;     while(!Q.empty())     {         cur=Q.front();取队首元素         Q.pop();出队         if(cur.x==k)return cur.y;//判断是否达到目的         nex.x=cur.x+1;//判断+1的操作是否合法         if(nex.x>=0&&nex.x<N&&a[nex.x]==0)         {             nex.y=cur.y+1;             a[nex.x]=1;             Q.push(nex);合法则入队并步数+1         }         nex.x=cur.x-1;         if(nex.x>=0&&nex.x<N&&a[nex.x]==0)         {             nex.y=cur.y+1;             a[nex.x]=1;             Q.push(nex);         }         nex.x=cur.x*2;         if(nex.x>=0&&nex.x<N&&a[nex.x]==0)         {             nex.y=cur.y+1;             a[nex.x]=1;             Q.push(nex);         }     }     return -1; } int main() {     int n;     while(~scanf("%d %d",&n,&k))     {         memset(a,0,sizeof(a));//多次运行，刷0；         int bs=bfs(n);         if(bs>=0)         printf("%d\n",bs);     }     return 0; }