【BFS】抓住那头牛

题目

1100. 抓住那头牛

---

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

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

农夫有两种移动方式：

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

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

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

输入格式

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

输出格式

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

数据范围

$0 \le N,K \le 10^5$

输入样例：

5 17

输出样例：

4

解题

方法一：BFS

思路

每一步可以走到 $x + 1$ 或 $x - 1$ 或 $x * 2$，在 $[0, 10^5]$ 的范围内宽搜，并记录步数，直到第一次遇到 $k$。

代码

#include <iostream>
#include <queue>

using namespace std;

const int N = 1e5 + 10;
int n, k;
bool vis[N];

int main() {
    scanf("%d%d", &n, &k);
    if (n > k) {
        printf("%d\n", n - k);
        return 0;
    }
    int step = 0;
    queue<int> que;
    que.push(n);
    vis[n] = true;
    while (!que.empty()) {
        int sz = que.size();
        while (sz--) {
            int x = que.front();
            que.pop();
            if (x == k) {
                printf("%d\n", step);
                return 0;
            }
            int nx = x + 1;
            if (nx >= 0 && nx < N && !vis[nx]) {
                que.push(nx);
                vis[nx] = true;
            }
            nx = x - 1;
            if (nx >= 0 && nx < N && !vis[nx]) {
                que.push(nx);
                vis[nx] = true;
            }
            nx = x << 1;
            if (nx >= 0 && nx < N && !vis[nx]) {
                que.push(nx);
                vis[nx] = true;
            }
        }
        ++step;
    }
    
    return 0;
}