【C++】鸡飞狗不跳

Question

题目描述
有一只鸡和一条狗，他们在一条线上，鸡的位置在点 NN 处，狗在点 MM 处，鸡和狗约定，狗站那不动，鸡去找狗。

鸡可以一次向左或向右走一步，也可一次飞到原来所在位置的 22 倍处。鸡飞一次和走一步时间相同。为了不让狗等，鸡最快多长时间能到狗的位置。

输入
输入一行 N,MN,M（ 0≤N,M≤1000000≤N,M≤100000 )。

输出
输出鸡到狗位置的最短时间。

样例
输入
5 17
输出
4

错误代码

#include<bits/stdc++.h>
using namespace std;
int main() {

    return 0;
}

Answer 1

让阿豪来帮你解答，本回答参考chatgpt3.5编写提供，如果还有疑问可以评论或留言

题目分析： 这道题目可以用广度优先搜索来解决。每次鸡可以进行两种操作：走一步或者飞两倍距离，所以可以将鸡到达每一个点的状态视为图中的一个节点，然后使用队列进行广度优先搜索，每次将鸡的状态进行更新并加入队列中。找到狗的位置即可停止搜索。 代码实现：

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int MAXN = 1e6 + 5;
int n, m;
int dist[MAXN]; // 记录每个点的最小距离
bool vis[MAXN]; // 记录每个点是否被访问过
int bfs() {
    queue<int> q;
    q.push(n);
    vis[n] = true;
    dist[n] = 0;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        if (cur == m) { // 找到狗了
            return dist[cur];
        }
        // 走一步
        int next_pos;
        next_pos = cur - 1;
        if (next_pos >= 0 && !vis[next_pos]) { // 不能出界，不能重复访问
            q.push(next_pos);
            vis[next_pos] = true;
            dist[next_pos] = dist[cur] + 1;
        }
        next_pos = cur + 1;
        if (next_pos <= 1000000 && !vis[next_pos]) {
            q.push(next_pos);
            vis[next_pos] = true;
            dist[next_pos] = dist[cur] + 1;
        }
        // 飞两倍距离
        next_pos = cur * 2;
        if (next_pos <= 1000000 && !vis[next_pos]) {
            q.push(next_pos);
            vis[next_pos] = true;
            dist[next_pos] = dist[cur] + 1;
        }
    }
    return -1; // 没有找到
}
int main() {
    memset(vis, false, sizeof(vis));
    cin >> n >> m;
    cout << bfs() << endl;
    return 0;
}