抓牛问题 - Catch That Cow

这个题目,我用的是BFS广度搜索来解题目的,毕竟也是一个最短连接问题.

Posted by isheng on July 16, 2016

抓牛问题之使用BFS解法

原题题目

B - Catch That Cow

Time Limit:2000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u

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.

我的思路

当我看到这个题目得时候,完全没有头绪,因为是B题,没有去看后面的BFS搜索,所以开始我也不知道怎么解,用什么方法来解这一道题目,等到后来做了几个关于迷宫最短路径问题的时候,我就发现这个题目好像有点类似求图中最短路径的问题,想到这里,我就马上用了BFS广度搜索算法建立了写出了这个题目,测试案例通过了,但等到我提交的时候,傻眼了,超出内存了。

调试过程

当知道超出内存后,我就通过Windows内置的进程控制程序,测试数据调到最大,运行程序,查看了一下我占用的内存大小,好像到了2个G系统自动的把它中断了,仔细想了一下,估计是边界条件判断出错,导致陷入了死循环中

问题代码
if(num <= k) {t_b.push(num);t_b.push(setup);b_tak[num] = false;}
//num为当前所在的步数

这个代码中if的判断参数只判断了步数小于等于最终牛的步数就继续递归搜索下去,然后我就加了一个条件,判断步数当前num必须大于0才有意义。

第一次改进后的代码
if(num <= k && num >= 0) {t_b.push(num);t_b.push(setup);b_tak[num] = false;}
//num为当前所在的步数

然后我就又提交了一次,竟然超时了,好吧,效率不过关呀!继续想思考,进行debug模式,发现我有很多重复的不是一直在进程中运行,这么多重复的递归导致效率好低,然后我就加了一个数组,通过数组来检测当前步数是否已经测试过了!

第二次改进后的代码
if(num <= k && num >= 0 && b_tak[num]) {t_b.push(num);t_b.push(setup);b_tak[num] = false;}
//num为当前所在的步数,b_tak[]判断当前节点是否已经访问过了。

最后提交终于过了,过程是曲折的,但是结果是感人的。

感想及其改进

感想就是OJ好坑爹,不过这次过程还是蛮顺利的,两次调试就过了,经验就是,在搜索算法中必须对不必要的分支剪出,这样会极大的提高效率。

最终AC代码

#include <iostream>
#include <cstdio>
#include <queue>
#define b_max 100010
using namespace std;

queue<int> t_b;//建立搜索队列
bool b_tak[b_max];//建立数组用于判断节点是否访问过了

int b_queue(int k){//BFS搜索核心,搜索最短时间抓到牛
    int num = 0,frint,setup = 0,ss = 0;
    while(ss <= k){//清空队列
        b_tak[ss] = true;
        ss++;
    }
    while(num != k){
        frint = t_b.front();
        t_b.pop();
        setup = t_b.front()+1;
        t_b.pop();
        for (int i = 0; i < 3; i++) {
            switch (i){
                case 0:
                    num = frint - 1;
                    break;
                case 1 :
                    num = frint + 1;
                    break;
                case 2:
                    num = frint * 2;
                    break;
            }
            if(num <= k && num >= 0 && b_tak[num]) {t_b.push(num);t_b.push(setup);b_tak[num] = false;}//对进入搜索队列的数据进行判断
            if(num == k) break;
        }
        if(num == k) break;//搜索停止的条件
    }
    while(!t_b.empty())
        t_b.pop();
    return setup;
}

int main(){
    int n,k;
//    freopen("in.txt", "r", stdin);
    while(scanf("%d %d",&n,&k)!=EOF){
        if(n >= k) {
            cout << n-k << endl;
            continue;}
        while(!t_b.empty())
            t_b.pop();
        t_b.push(n);
        b_tak[n] = false;
        t_b.push(0);
        cout << b_queue(k) <<endl;
    }
}

好啦,Coding是一件很有趣的事情!