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;
    
}           

複制