头像

上善若水_


访客:323

离线:1个月前



题目描述

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

农夫有两种移动方式:

从 X 移动到 X−1 或 X+1 ,每次移动花费一分钟
从 X 移动到 2∗X ,每次移动花费一分钟
假设牛没有意识到农夫的行动,站在原地不动。

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

输入格式
共一行,包含两个整数N和K。

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

数据范围
0≤N,K≤105

样例

输入样例:
5 17
输出样例:
4


算法

广度优先搜索(深度优先搜索)

bfs:
特判:若终点小于起点只有倒退一种走法,直接输出差值。

常规:开两队列,分别储存到达的点和最短到达的时间。
(可用book数组记录访问过的值,避免一个数被重复压入队列)

dfs:
同理上。
此题上性能不如bfs好,故不推荐。

C++ 代码

#include<iostream>
#include<queue>
#include<algorithm>

using namespace std;

int n,m;
int g[100010]={};

int check(int x,int y){//两种情况判断

    if(x==1) return x;
    return y;
}

void bfs(){
    queue<int> ans;
    queue<int> qx;
    qx.push(n);
    ans.push(0);
    while(!qx.empty()){
        for(int i=1;i<=2;i++){
            int tx=qx.front()+check(i,qx.front());
            if(tx>=0 && tx<m){//判断边界
                qx.push(tx);//满足就压入
                ans.push(ans.front()+1);
            }
            if(tx==m){//到达终点直接输出并返回
                int k=ans.front()+1;
                cout<<k;//输出结果
                return;
            }
        }
        qx.pop(),ans.pop();
    }
}

int main(){
    cin>>n>>m;

    if(m<=n) cout<<n-m;//首先特判起点和终点我位置关系,先解决起点小于终点的简单情况
    else bfs();

    return 0;
}