Catch That Cow（广度优先搜索）

题目连接

http://poj.org/problem?id=3278

输入

5 17

结果

4

农民约翰到达逃犯牛最快的方式是沿着以下路径：5-10-9-18-17，需要4分钟。

(1).向后-1    (2).向前+1    (3).向前2*x

广度优先搜索练习，BFS

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#define maxn 100010

using namespace std;

int s[maxn],v[maxn];
queue<int>Q;

int BFS(int n,int k)
{
    int start,step;
    Q.push(n);
    v[n]=1;
    s[n]=0;
    while(!Q.empty())
    {
        start=Q.front();
        Q.pop();
        for(int i=0; i<=2; i++)
        {
            if(i==0)
                step=start-1;
            else if(i==1)
                step=start+1;
            else if(i==2)
                step=start*2;
            if(step>=maxn || step<0)
                continue;
            if(!v[step])
            {
                Q.push(step);
                v[step]=1;
                s[step]=s[start]+1;
            }
            if(step==k)
                return s[step];
        }
    }
}

int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    if(n>=k)
        printf("%d
",n-k);
    else
        printf("%d
",BFS(n,k));

    return 0;
}