首页 > 代码库 > POJ 3278 Catch That Cow
POJ 3278 Catch That Cow
Catch That Cow
Time Limit: 2000ms
Memory Limit: 65536KB
This problem will be judged on PKU. Original ID: 327864-bit integer IO format: %lld Java class name: Main
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
Source
USACO 2007 Open Silver
解题：搜。。。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib>10 #include <string>11 #include <set>12 #include <stack>13 #define LL long long14 #define pii pair<int,int>15 #define INF 0x3f3f3f3f16 using namespace std;17 struct node{18 int p,step;19 node(int x = 0,int y = 0):p(x),step(y){}20 };21 int n,k;22 bool vis[100100];23 queue<node>q;24 int bfs(){25 while(!q.empty()) q.pop();26 memset(vis,false,sizeof(vis));27 vis[n] = true;28 q.push(node(n,0));29 int tmp;30 while(!q.empty()){31 node now = q.front();32 q.pop();33 if(now.p == k) return now.step;34 tmp = now.p+1;35 if(tmp <= 100000 && !vis[tmp]){36 vis[tmp] = true;37 q.push(node(tmp,now.step+1));38 }39 tmp = now.p-1;40 if(tmp >= 0 && !vis[tmp]){41 vis[tmp] = true;42 q.push(node(tmp,now.step+1));43 }44 tmp = now.p<<1;45 if(tmp <= 100000 && !vis[tmp]){46 vis[tmp] = true;47 q.push(node(tmp,now.step+1));48 }49 }50 return -1;51 }52 int main() {53 while(~scanf("%d %d",&n,&k))54 printf("%d\n",bfs());55 return 0;56 }
POJ 3278 Catch That Cow
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。