/**//*
bfs+剪枝典型简单题，注意此题设置的方向动态确定，且要判断，是否左大于右。
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <memory.h>
#include <cmath>
#include <bitset>
#include <queue>
#include <vector>
using namespace std;
const int MAXN =100400;
const int INF =0x4ffffff;
#define CLR(x,y) memset(x,y,sizeof(x))
#define ADD(x) x=((x+1)&BORDER)
#define IN(x) scanf("%d",&x)
#define OUT(x) printf("%d\n",x)
#define MIN(m,v) (m)<(v)?(m):(v)
#define MAX(m,v) (m)>(v)?(m):(v)
#define ABS(x) ((x)>0?(x):-(x))
struct node
{
int x;
int step;
node():x(0),step(0){}
};
int vis[MAXN*2];
int sum,n,ans;
int main()
{
int n,k,i,min=999999;
int dir[4]={-1,1};
node start,end,tmp,next;
queue<node> que;
scanf("%d%d",&start.x,&end.x);
que.push(start);
vis[start.x]=1;
if(start.x>end.x)min=start.x-end.x;
else
while(!que.empty())
{
tmp=que.front();
que.pop();
dir[2]=tmp.x;
//dir[3]=2*tmp.x;
for(i=0;i<3;++i)
{
next.x=tmp.x+dir[i];
if(next.x>=0&&next.x<=end.x*3&&next.x<=MAXN&&tmp.step<min&&!vis[next.x])
{
next.step=tmp.step+1;
if(next.x==end.x)min=min>next.step?next.step:min;
que.push(next);
vis[next.x]=1;
}
}
}
memset(vis,0,sizeof(vis));
if(min==999999)min=0;
printf("%d\n",min);
min=999999;
}
Catch That Cow
| Time Limit: 2000MS |
|
Memory Limit: 65536K |
| Total Submissions: 23446 |
|
Accepted: 7185 |
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.