POJ 3278 Catch That Cow BFS

题目连接 http://poj.org/problem?id=3278

一开始作者道题的时候re了好几次。不知道为什么后来交的时候又WA然后发现得分情况一种是大于等于一种是小于

一天刚学会就A了三道题比较满意。

#include<stdio.h>
#include<string.h>
struct node 
{
    int step;
    int i;
}q[500005];
int pro[500005];
int fro,re;
int main()
{
    int farm,cow;
    while(scanf("%d %d",&farm,&cow) != EOF)
    {
        int i,j,k,num;
        memset(pro,0,sizeof(pro));
        pro[farm] = 1;
        fro  = 0;
        re = 0;
        q[re++].i = farm;
        q[fro].step = 0;
        int leap = 1;
        if(farm >= cow)
        {
            printf("%d\n",farm-cow);
        }
        else
        {
        while(fro != re)
        {
            int v;
            v = q[fro].i;
            if(v == cow)
            {
                leap = 0;
                break;
            }
            num = q[fro].step;
            fro++;
            for(i = 1;i <= 3;i++)
            {
                if(i == 1)
                {
                    k = v+1;
                }
                if(i == 2)
                {
                    k = v-1;
                }
                if(i == 3)
                {
                    k = 2*v;
                }
                if(k <= 500005 && k >= 0 && !pro[k])
                {
                    q[re].i = k;
                    q[re].step += num+1;
                    if(k == cow)
                    {
                        leap = 0;
                        break;
                    }
                    re++;
                    pro[k] = 1;
                }
            }
            if(!leap)
                break;
        }
        if(leap)
            puts("NO");
        else
            printf("%d\n",q[re].step);
        }
    }
    return 0;
}