首页 > 代码库 > poj 3278
poj 3278
Catch That Cow
Time Limit: 2000MS | Memory Limit: 65536K | |
Total Submissions: 43851 | Accepted: 13674 |
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
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.
Source
USACO 2007 Open Silver
#include<iostream> #include<algorithm> #include<cstring> #include<queue> using namespace std; struct Node{ int x,t; Node(int X,int T){ x=X; t=T; } }; int sign[200010]; //注意这里的标记数组要定大一些,定为100010会runtime error int ans; queue <Node> q; int main(){ int n,k; while(cin>>n>>k){ ans=9999999; memset(sign,0,sizeof(sign)); while(!q.empty()) q.pop(); //清空队列 int x,t; x=n; t=0; q.push(Node(x,t)); //入队 sign[x]=1; //标记已访问 while(!q.empty()){ x=q.front().x; t=q.front().t; q.pop(); if(x==k) ans=min(ans,t); else{ if(x<k){ if(sign[x+1]==0){ q.push(Node(x+1,t+1)); sign[x+1]=1; } if(sign[2*x]==0){ q.push(Node(2*x,t+1)); sign[2*x]=1; } if(x>0&&sign[x-1]==0){ q.push(Node(x-1,t+1)); sign[x-1]=1; } } else if(x>k){ if(sign[x-1]==0){ q.push(Node(x-1,t+1)); sign[x-1]=1; } } } } cout<<ans<<endl; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。