我是靠谱客的博主 坚强鲜花,最近开发中收集的这篇文章主要介绍poj 3278 Catch That Cow,觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

Catch That Cow
Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 100270 Accepted: 31366
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.

题意:从x走到y点,每一步都有三种方案,走到2倍的位子或者加1或者减1。

思路:找的是最短的走法,是广搜的模版题。

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<queue>
#include<string>
using namespace std;
struct node
{
int x,l;
} nod[100010];
int n,k,ans;
int vis[200010];
int bfs()
{
queue<node>q;
while(!q.empty())
q.pop();
vis[n]=1;
node t;
t.x=n;
t.l=0;
q.push(t);
while(!q.empty())
{
t=q.front();
q.pop();
if(t.x==k)
return t.l;
for(int j=0; j<3; j++)
{
node T=t;
if(j==0)
{
T.x*=2;
T.l+=1;
}
if(j==1)
{
T.x+=1;
T.l+=1;
}
if(j==2)
{
T.x-=1;
T.l+=1;
}
if(T.x==k)
return T.l;
if(T.x<200005&&T.x>=0&&vis[T.x]==0)
{
vis[T.x]=1;
q.push(T);
}
}
}
return 0;
}
int main()
{
while(~scanf("%d%d",&n,&k))
{
memset(vis,0,sizeof(vis));
cout<<bfs()<<endl;
}
}



最后

以上就是坚强鲜花为你收集整理的poj 3278 Catch That Cow的全部内容,希望文章能够帮你解决poj 3278 Catch That Cow所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(56)

评论列表共有 0 条评论

立即
投稿
返回
顶部