| Catch That Cow
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 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 Sample Output 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 |
题意:
在一个数轴上,给你一个起始点和终点,问你从起点走到终点最少需要多少步.你可以单步走也可以double跳跃.
其中单步走指你当前位置在x上，那么你下一步可以走到x+1或x-1位置上。
double跳跃指，你当前位置在x上，那么你下一步可以走到2*x位置上。
分析:
典型的BFS,不过注意点的坐标范围是[0,100000].
当起点s在终点e右边时，直接输出s-e即可。
其他情况则需要BFS搜索三种情况了
This is the codes：
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<iomanip>
#include<list>
#include<map>
#include<queue>
#include<sstream>
#include<stack>
#include<string>
#include<set>
#include<vector>
using namespace std;
#define PI acos(-1.0)
#define EPS 1e-8
#define MOD 1e9+7
#define LL long long
#define ULL unsigned long long //1844674407370955161
#define INT_INF 0x7f7f7f7f //2139062143
#define LL_INF 0x7f7f7f7f7f7f7f7f //9187201950435737471
const int dr[]={0, 0, -1, 1, -1, -1, 1, 1};
const int dc[]={-1, 1, 0, 0, -1, 1, -1, 1};
// ios::sync_with_stdio(false);
// 那么cin, 就不能跟C的 scanf，sscanf, getchar, fgets之类的一起使用了。
int dis[100005];
bool v[100005];
int BFS(int n,int k)
{queue<int> q;q.push(n);v[n]=true;dis[n]=0;while(!q.empty()){int x=q.front();q.pop();for(int i=0;i<3;++i){int nx;if(i==0)//暴力枚举每种情况nx=x+1;else if(i==1)nx=x-1;elsenx=x*2;if(nx>=0&&nx<=100000&&!v[nx]){v[nx]=true;dis[nx]=dis[x]+1;q.push(nx);}}}return dis[k];
}
int main()
{int n,k;scanf("%d%d",&n,&k);if(n>=k) //特殊情况{printf("%d\n",n-k);return 0;}int ans=BFS(n,k);printf("%d\n",ans);return 0;
}