Catch That Cow

农夫知道一头牛的位置,想要抓住它。农夫和牛都于数轴上 ,农夫起始位于点 N(0<=N<=100000) ,牛位于点 K(0<=K<=100000) 。农夫有两种移动方式: 1、从 X移动到 X-1或X+1 ,每次移动花费一分钟 2、从 X移动到 2*X ,每次移动花费一分钟 假设牛没有意识到农夫的行动,站在原地不。最少要花多少时间才能抓住牛?Input

一行: 以空格分隔的两个字母: N 和 K

Output

一行: 农夫抓住牛需要的最少时间,单位分钟

Sample Input

5 17

Sample Output

4

Hint

农夫使用最短时间抓住牛的方案如下: 5-10-9-18-17, 需要4分钟.     思路:简单广搜题,用队列处理农夫的位置,用数组来存储状态(该点是否已经来过,是第几分钟到的。)因为只有三种移动方式,处理时也快。代码如下:
#include <iostream>
#include <algorithm>
#include <math.h>
#include <queue>
#include <string.h>
const int max_n = 100002;
using namespace std;
int used[max_n];
queue<int> que;
int bfs(int n, int k)
{
    int d, date;//d为经过移动后的位置,date为队首元素的位置
    que.push(n);//将农夫位置入队
    used[n] = 1;//初始化用了1分钟,因为进行搜索前将数组初始化为0了,这里用1以示区别
    while (!que.empty())//当队列非空时
    {
        date = que.front(); que.pop();//记录当前位置
        for (int i = 0; i < 3; i++)//三种移动方式
        {
            if (i == 0)d = date - 1;
            if (i == 1)d = date + 1;
            if (i == 2)d = date * 2;
            if (d >= 0 && d < 100001 && used[d] == 0)//符合条件的加入队列,即没有去过的点
            {
                que.push(d);
                used[d] = used[date] + 1;//数组记录到该点用了多少分钟
                if (d == k) return used[d]-1;//从1开始计数的,所以-1
            }
        }
    }
}
int main()
 {
    int n, k;
    scanf ("%d %d", &n, &k);
    if(n>=k)printf("%d\n",n-k);//如果农夫在牛前面,只能向后走,就不用搜索了
    else {
        memset(used,0,sizeof(used)); 
        int sum=bfs(n, k);
        printf("%d\n", sum);
    }
    return 0;
}

 

上一篇:POJ 3278 Catch That Cow


下一篇:Codeforces 283E Cow Tennis Tournament 线段树 (看题解)