AcWing 1100. 抓住那头牛 BFS

农夫知道一头牛的位置，想要抓住它。

农夫和牛都位于数轴上，农夫起始位于点 N，牛位于点 K。

农夫有两种移动方式：

1. 从 X 移动到 X−1或 X+1，每次移动花费一分钟
2. 从 X 移动到 2X，每次移动花费一分钟

假设牛没有意识到农夫的行动，站在原地不动。

农夫最少要花多少时间才能抓住牛？

输入格式

共一行，包含两个整数N和K。

输出格式

输出一个整数，表示抓到牛所花费的最少时间。

数据范围

输入样例：

5 17           

复制

输出样例：

4           

复制

BFS,老水题了，还是一维的。。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
#define x first
#define y second
typedef pair<int,int> pii;
int n,k,vis[N];
void bfs(int x){
    queue<pii>q;
    q.push({x,0});
    while(!q.empty()){
        auto now=q.front();
        vis[now.x]=1;
        q.pop();
        if(now.x==k){
            cout<<now.y<<endl;
            return;
        }
        if(now.x+1<=100000&&!vis[now.x+1]){
            vis[now.x+1]=1;
            q.push({now.x+1,now.y+1});
        }
        if(now.x-1>=0&&!vis[now.x-1]){
            vis[now.x-1]=1;
            q.push({now.x-1,now.y+1});
        }
        if(now.x*2<=100000&&!vis[now.x*2]){
            vis[now.x*2]=1;
            q.push({now.x*2,now.y+1});
        }
    }
}
int main(){
    cin>>n>>k;
    bfs(n);
    return 0;
    
}           

复制