C - 青铜五 HDU - 2717 Catch That Cow BFS-白红宇

C - 青铜五 HDU - 2717 Catch That Cow BFS

阅读量：7078 次

发布时间：2019-06-28

本文共 2060 字，大约阅读时间需要 6 分钟。

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.

题意：一维地图上有两个点，最少多少步可以从起点到终点；人可以：1.向左或右走一步；2.直接从当前位置x传送到2*x

搜索，没啥好说的

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              typedef long long LL;typedef long double LD;using namespace std;const int maxn=100000*2;int vis[maxn];int f[8][2]={ {-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};int n,m;struct node{ int x; int step;};queue
              
               q;void bfs(node st,node en){ q.push(st); //printf("*****\n"); while(!q.empty()) { node t=q.front(); //printf("%d %d\n",t.x,t.step); q.pop(); if(t.x==en.x) { printf("%d\n",t.step); return; } if(t.x+1<=en.x&&vis[t.x+1]==0) { q.push((node){t.x+1,t.step+1}); vis[t.x+1]=1; } if(t.x-1>=0&&vis[t.x-1]==0) { q.push((node){t.x-1,t.step+1}); vis[t.x-1]=1; } if(t.x*2<=2*en.x&&vis[t.x*2]==0) { q.push((node){t.x*2,t.step+1}); vis[t.x*2]=1; } }}int main(){ int N,K; while(~scanf("%d%d",&N,&K)) { //printf("$$$$$$$$$$$$\n"); node st,en; st.x=N; st.step=0; en.x=K; memset(vis,0,sizeof(vis)); vis[N]=1; while(!q.empty())q.pop(); bfs(st,en); } return 0;}