周六900C++班级2022-10-29 广搜

7588: 农夫抓牛

农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点N(0<=N<=100000)，牛位于点K(0<=K<=100000)。农夫有两种移动方式：

1、从X移动到X-1或X+1，每次移动花费一分钟

2、从X移动到2*X，每次移动花费一分钟

假设牛没有意识到农夫的行动，站在原地不动。农夫最少要花多少时间才能抓住牛？

#include<bits/stdc++.h>
using namespace std;
struct node{
    int x,y,step;
};
node q[100005];
int nex[3] = {-1,1,2};
int vis[100005]; //标记数组 
int n,k,f,ans; //f终点的标记 
void bfs()
{
    int head = 1,tail = 1;
    q[tail].x = n;
    q[tail].step = 0;
    tail++; //扩充队尾
    vis[n] = 1; //标记起点
    while(head<tail)
    {
        for(int i=0;i<3;i++)
        {
            int tx;
            if(i<2) tx = nex[i]+q[head].x; //方向数组+队首head的位置 
            else tx = nex[i]*q[head].x;
            if(tx>100000 || tx<0) continue;//越界判断
            if(vis[tx]==0) //vis数组里没标记过，那么就让tx加入队尾
            {
                vis[tx] = 1; //标记tx
                q[tail].x = tx;
                q[tail].step = q[head].step+1; 
                tail++; //扩充队列长度 
            } 
            if(tx==k){ //找到终点 
                f = 1;
                ans = q[tail-1].step;
                break;
            }
        }
        if(f)break;
        head++; //队首往后一位 
    } 
}
int main()
{
    cin>>n>>k; //输入起点终点 
    bfs(); //寻找最短路 
    cout<<ans; //输出最短路长 
     return 0;
}