BFS【啊哈磊-抓住那头牛】

标题:

抓住那头牛

标签:

搜索广度优先搜索

详情:

农民约翰的农场有一头逃亡了。现在已知的牛的位置并立即想抓住她。约翰从的起始点为S,牛目前在点K。农民约翰有两种行进方式:步行和传送。

*走:约翰可以从任何点X，走到X-1或 X+1，耗时一分钟。
*传送:约翰可以从任何点的X，传送到点2X，耗时一分钟。

输入格式:

只有一行包含两个整数S和K

输出格式:

输出一个整数，表示农民约翰需要在几分钟内抓逃犯牛。

限制:

0<=S<=100000
0<=K<=100000

样例:

输入

5 17

输出

解释

农民约翰的最快的方式到达逃亡的位置式沿着以下路径:5-10-9-18-17,需要4分钟。

题解：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define INF 99999999
using namespace std;
const int maxn=100005;
int vis[maxn];
int S,K;
int minx=INF;
int dir[3][1]={-1,1,2};
typedef struct Node{
    int x;
    int step;
}node;
void bfs(int x){
    queue<node> q;
    node p,t;
    p.x=x;
    p.step=0;
    vis[p.x]=1;
    q.push(p);
    while(!q.empty()){
        p=q.front();
        q.pop();
        if(p.x==K){
            if(p.step<minx){
                minx=p.step;
            }
        }
        for(int i=0;i<3;i++){
            if(p.x-1>=0&&!vis[p.x-1]){
                t.x=p.x-1;
                t.step=p.step+1;
                vis[t.x]=1;
                q.push(t);
            }
            if(p.x+1<=100000&&!vis[p.x+1]){
                t.x=p.x+1;
                t.step=p.step+1;
                vis[t.x]=1;
                q.push(t);
            }
            if(p.x*2<=100000&&!vis[p.x*2]){
                t.x=p.x*2;
                t.step=p.step+1;
                vis[t.x]=1;
                q.push(t);
            }
        }
    }
}
int main()
{
    scanf("%d %d",&S,&K);
    bfs(S);
    printf("%d
",minx);
    return 0;
}