侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 551 篇文章
  • 累计创建 117 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【BFS】抓住那头牛

GabrielxD
2022-12-20 / 0 评论 / 0 点赞 / 14 阅读 / 447 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-12-20,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

1100. 抓住那头牛


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

农夫和牛都位于数轴上,农夫起始位于点 NN ,牛位于点 KK

农夫有两种移动方式:

  1. XX 移动到 X1X-1X+1X+1 ,每次移动花费一分钟
  2. XX 移动到 2X2*X ,每次移动花费一分钟

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

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

输入格式

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

输出格式

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

数据范围

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

输入样例:

5 17

输出样例:

4

解题

方法一:BFS

思路

每一步可以走到 x+1x + 1x1x - 1x2x * 2,在 [0,105][0, 10^5] 的范围内宽搜,并记录步数,直到第一次遇到 kk

代码

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

评论区