首页 > 代码库 > poj 3278 -- Catch That Cow

poj 3278 -- Catch That Cow

2024-07-15 12:46:29   215人阅读

Catch That Cow
Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 46279 Accepted: 14508

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 pointK (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  *           Author :   kevin 3  *         Filename :   CatchThatCow.cpp 4  *       Creat time :   2014-08-03 10:06 5  *      Description : 6 ========================================================================*/ 7 #include <iostream> 8 #include <algorithm> 9 #include <cstdio>10 #include <cstring>11 #include <queue>12 #include <cmath>13 #define clr(a,b) memset(a,b,sizeof(a))14 #define M 20000515 using namespace std;16 int vis[M],cnt[M];17 18 void BFS(int m,int n)19 {20     queue<int>que;21     vis[m]=1;22     que.push(m);23     while(que.front()!=n && !que.empty()){24         int t=que.front();25         que.pop();26         if(!vis[t-1] && (t-1>=0 && t-1<M)){27             que.push(t-1);28             cnt[t-1]=cnt[t]+1;29             vis[t-1]=1;30         }31         if(!vis[t+1] && (t+1>=0 && t+1<M)){32             que.push(t+1);33             cnt[t+1]=cnt[t]+1;34             vis[t+1]=1;35         }36         if(!vis[t*2] && (t*2>=0 && t*2<M)){37             que.push(t*2);38             cnt[t*2]=cnt[t]+1;39             vis[t*2]=1;40         }41     }42 }43 44 int main()45 {46     int n,k;47     while(scanf("%d%d",&n,&k)!=EOF){48         clr(vis,0);49         clr(cnt,0);50         BFS(n,k);51         printf("%d\n",cnt[k]);52     }53     return 0;54 }
View Code

 


联系
我们