Blog·Tanky WooABOUTRSS

HDU/HDOJ 2717 Catch That Cow(BFS)

22 Nov 2011
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

题目链接:

http://acm.hdu.edu.cn/showproblem.php?pid=2717

基本的BFS,注意在Teleporting时,考虑if的条件,具体见代码:

#include 
#include 
using namespace std;

int N, K;
int line[100005];

void BFS()
{
    queue que;
    que.push(N);
    line[N] = 1;

    while(!que.empty())
    {
        int tmp = que.front();
        que.pop();

        if(tmp == K)
            break;

        int next = tmp-1;
        if(next>=0 && !line[next])
        {
            que.push(next);
            line[next] = line[tmp] + 1;
        }

        next = tmp+1;
        if(next>=0 && !line[next])
        {
            que.push(next);
            line[next] = line[tmp] + 1;
        }

        next = tmp*2;
        if(next<=100000 && !line[next] && next-K= K)
            line[K] = N-K+1;
        else
            BFS();
        printf("%d\n", line[K]-1);

    }

}