首页 > 代码库 > poj 3278 Catch That Cow(bfs)
poj 3278 Catch That Cow(bfs)
Catch That Cow
Time Limit: 2000MS | Memory Limit: 65536K | |
Total Submissions: 49503 | Accepted: 15506 |
Description
Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a pointN (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 orX + 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 andK
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
题意:
求最小步数使N转换成K。可以:N=N-1,N=N+1,N=N×2;
CODE:
题意:
求最小步数使N转换成K。可以:N=N-1,N=N+1,N=N×2;
CODE:
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<string> #include<algorithm> #include<cstdlib> #include<set> #include<queue> #include<stack> #include<vector> #include<map> #define N 100010 #define Mod 10000007 #define lson l,mid,idx<<1 #define rson mid+1,r,idx<<1|1 #define lc idx<<1 #define rc idx<<1|1 const double EPS = 1e-11; const double PI = acos(-1.0); typedef long long ll; const int INF=1000010; using namespace std; int a[N],b[N]; queue<int>mp; int bfs(int k,int n) { mp.push(k); b[k]=1; int mans; while(mp.size()) { mans=mp.front(); mp.pop(); if(mans==n) break; if((mans-1)>=0&&!b[mans-1]) { mp.push(mans-1); a[mans-1]=a[mans]+1; b[mans-1]=1; } if((mans+1)<=100000&&!b[mans+1]) { mp.push(mans+1); a[mans+1]=a[mans]+1; b[mans+1]=1; } if((mans*2)<=100000&&!b[mans*2]) { mp.push(mans*2); a[mans*2]=a[mans]+1; b[mans*2]=1; } } return a[n]; } int main() { int k,n; while(cin>>k>>n) { if(n<=k) printf("%d\n",k-n); else { memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); printf("%d\n",bfs(k,n)); } } return 0; }
poj 3278 Catch That Cow(bfs)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。