POJ 3278 Catch That Cow (BFS)-蒲公英云

POJ 3278 Catch That Cow (BFS)

题意：给你两个数N（代表农夫John）和K（他的奶牛的位置） John每次有三种移动方式 1.向左移动一格 2.向右移动一格 3.移动到现在位置的2倍下标的位置，奶牛是静止的，问你John最少需要多少步走到奶牛所在的位置。

分析：因为是求最少的步数，所以直接可以用BFS来求解这题在复习的时候又写了一次一直RE，想了好久，最后发现了一个问题，如果是先判断当前下标是否标记的话，则需要将数组的大小开到题目要求的二倍，但如果是先判断是否越界的话，对于&&运算，当前面不成立的时候就不会执行后面的运算了，所以如果是先判断是否越界的话就不会RE。

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<utility>
#include<cctype>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define inf 0x3f3f3f3f
#define Clear(x) memset(x,0,sizeof(x))
#define fup(i,a,b) for(int i=a;i<b;i++)
#define rfup(i,a,b) for(int i=a;i<=b;i++)
#define fdn(i,a,b) for(int i=a;i>b;i--)
#define rfdn(i,a,b) for(int i=a;i>=b;i--)
typedef long long ll;
using namespace std;
const double pi=acos(-1.0);
const int maxn = 1e5+5;
int N,K;
int vis[maxn];
struct node{
    int x,step;
};
node vs,zb,nzb;
int BFS()
{
    Clear(vis);
    queue<node>q;
    while(!q.empty()) q.pop();
    vs.x=N,vs.step=0;
    vis[N]=1;
    q.push(vs);
    while(!q.empty())
    {
        zb = q.front();
        q.pop();
        if(zb.x==K) return zb.step;
                if(zb.x-1>=0&&!vis[zb.x-1])
        {
            vis[zb.x-1] = 1;
            nzb.x = zb.x-1;
            nzb.step = zb.step+1;
            q.push(nzb);
        }
        if(zb.x+1<=100000&&!vis[zb.x+1])
        {
            vis[zb.x+1] = 1;
            nzb.x = zb.x+1;
            nzb.step = zb.step+1;
            q.push(nzb);
        }
        if(zb.x*2<=100000&&!vis[zb.x*2])
        {
            vis[zb.x*2] = 1;
            nzb.x = zb.x*2;
            nzb.step = zb.step +1;
            q.push(nzb);
        }
    }
    return 0;
}
int main()
{
    while(scanf("%d%d",&N,&K)==2)
    {
        printf("%d\n",BFS());
    }
    return 0;
}