Catch That Cow

分析

BFS 直接来

这道题目是典型的最短路径问题，在算法分类中属于广度优先搜索 (BFS, Breadth-First Search) 的经典应用。

1 算法核心思路：为什么用 BFS？

在这个问题中，我们要寻找从点 $N$ 到点 $K$ 的最少时间。

每个位置可以看作图的一个节点。
每种移动方式（ $X-1,X+1,2X$ ）可以看作权重为 $1$ 的边。
BFS 的特性：在所有边权重相等的情况下，BFS 第一次到达目标节点时，走过的路径一定是最短的。

2 解题步骤与逻辑

状态定义：使用一个队列 queue 存储当前到达的位置，使用一个数组 dist[100001] 存储到达每个点所需的最短时间（同时起到标记是否访问过的作用）。
边界处理：
- 如果 $N\ge K$ ，农夫只能通过每分钟 $-1$ 的方式走向牛，最快时间直接就是 $N-K$ 。
- 搜索范围限定在 $\left[0,100,000\right]$ 之间。
搜索过程：
- 将起始点 $N$ 入队。
- 不断从队列中取出当前位置 $X$ 。
- 尝试三种移动： $X-1,X+1,2X$ 。
- 如果新位置有效且未被访问过，记录时间并入队。
- 一旦到达 $K$ ，立即返回结果。

代码

cpp

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

const int MAXN = 100005;
int dist[MAXN]; // 记录到达每个位置所需的最少时间

int bfs(int n, int k) {
    // 特殊情况：农夫在牛后面，只能往回走
    if (n >= k) return n - k;

    queue<int> q;
    memset(dist, -1, sizeof(dist)); // -1 表示尚未访问

    q.push(n);
    dist[n] = 0;

    while (!q.empty()) {
        int curr = q.front();
        q.pop();

        // 尝试三种移动方式
        int next_moves[3] = {curr - 1, curr + 1, curr * 2};

        for (int i = 0; i < 3; ++i) {
            int next = next_moves[i];

            // 检查边界及是否访问过
            if (next >= 0 && next < MAXN && dist[next] == -1) {
                dist[next] = dist[curr] + 1;
                
                // 找到目标，直接返回
                if (next == k) return dist[next];
                
                q.push(next);
            }
        }
    }
    return 0;
}

int main() {
    int n, k;
    while (cin >> n >> k) {
        cout << bfs(n, k) << endl;
    }
    return 0;
}

目录

分析

1 算法核心思路：为什么用 BFS？

2 解题步骤与逻辑

代码