AcWing算法提高课-2.2.3抓住那头牛

算法提高课整理

CSDN个人主页：更好的阅读体验

---

本文同步发表于 CSDN | 洛谷 | AcWing | 个人博客

原题链接

题目描述

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

农夫和牛都位于数轴上，农夫起始位于点 $n$，牛位于点 $k$。

农夫有两种移动方式：

1. 从 $x$ 移动到 $x?1$ 或 $x+1$，每次移动花费一分钟
2. 从 $x$ 移动到 $2x$，每次移动花费一分钟

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

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

输入格式

共一行，包含两个整数 $n$ 和 $k$。

输出格式

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

数据范围

$0\le n,k\le 10^5$

输入样例：

5 17

输出样例：

4

---

思路

要求时间最短，考虑 BFS。

分三种情况考虑即可，注意不要越界。

思路较简单，直接上代码。

算法时间复杂度

AC Code

$\text{C}++$

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010;

int n, k;
int q[N], dist[N];

int bfs()
{
    memset(dist, -1, sizeof dist); // -1 表示没走到过
    dist[n] = 0; // 起点距离为 0
    q[0] = n; // 起点入队
    
    int hh = 0, tt = 0;
    while (hh <= tt)
    {
        int t = q[hh ++ ];
        if (t == k) return dist[k]; // 如果走到终点, 返回用时
        
        if (t + 1 < N && dist[t + 1] == -1) // 三种情况，分别判断越界
        	dist[t + 1] = dist[t] + 1, q[ ++ tt] = t + 1;
        if (t - 1 >= 0 && dist[t - 1] == -1)
        	dist[t - 1] = dist[t] + 1, q[ ++ tt] = t - 1;
        if (t * 2 < N && dist[t * 2] == -1)
        	dist[t * 2] = dist[t] + 1, q[ ++ tt] = t * 2;
    }
    
    return -1; // 走不到返回 -1
}

int main()
{
    scanf("%d%d", &n, &k);
    printf("%d\n", bfs());
    
    return 0;
}

---

最后，如果觉得对您有帮助的话，点个赞再走吧！