【BZOJ1646】[Usaco2007 Open]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 * 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?

农夫约翰被通知,他的一只奶牛逃逸了!所以他决定,马上幽发,尽快把那只奶牛抓回来.

他们都站在数轴上.约翰在 N(O≤N≤100000) 处,奶牛在 K(O≤K≤100000) 处.约翰有两种办法移动,步行和瞬移:步行每秒种可以让约翰从 z 处走到 x+l 或 x-l 处;而瞬移则可让他在 1 秒内从 x 处消失,在 2x 处出现.然而那只逃逸的奶牛,悲剧地没有发现自己的处境多么糟糕,正站在那儿一动不动.

那么,约翰需要多少时间抓住那只牛呢?

输入格式 InputFormat

Line 1: Two space-separated integers: N and K.

仅有两个整数 N 和 K.

输出格式 OutputFormat

Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.

最短的时间.

样例输入 SampleInput

123 999

样例输出 SampleOutput

6

来源 Source

Silver


BZOJ 1646


代码 Code

BFS.

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define inf 0x7fffffff/27.11
const int maxN=200000;
int a[200005];
int f[1000005];
int i,j,t,n,m,l,r,k,z,y,x;
void add(int s)
{
    f[++r]=s;
    a[s]=a[f[l]]+1;
}
void bfs()
{
    int i,j,t;
    l=0;r=0;f[0]=n;a[n]=0;
    while (r>=l)
    {
        if (f[l]==k) return ;
        t=f[l]+1;if (t<=maxN && a[t]>a[f[l]]+1) add(t);
        t=f[l]-1;if (t>=0 && a[t]>a[f[l]]+1) add(t);
        t=f[l]*2;if (t<=maxN && a[t]>a[f[l]]+1) add(t);
        l++;
    }
}
int main()
{
    scanf("%d%d",&n,&k);
    for (i=0;i<=200001;i++) a[i]=inf;
    bfs();
    printf("%dn",a[k]);
    return 0;
}