题意分析

这道题目要求农夫 John 在数轴上从位置 N 出发，通过步行（X-1 或 X+1）或传送（2*X）的方式，以最少的时间到达奶牛所在的位置 K。奶牛不会移动，因此只需要计算 John 的最短路径时间。

解题思路

1. BFS（广度优先搜索）：由于每次移动的代价相同（1 分钟），BFS 天然适合求解最短路径问题。
2. 状态表示：当前位置 X 是一个状态，每次可以转移到 X-1、X+1 或 2*X。
3. 剪枝优化：
   • 如果 X 超出 [0, 1e5] 范围，则跳过（因为题目限制 N, K ≤ 1e5）。
   • 使用 vis 数组记录是否访问过某个点，避免重复计算。
4. 终止条件：当 X == K 时，返回当前步数。

代码示例

#include <cstdio>
#include <cstring>
#include <map>
#include <queue>
using namespace std;

int n, k, ans;
const int maxn = 1e5 + 5, INF = -1;
int step[maxn];      // step[i] 表示到达位置 i 所需的最少时间
bool vis[maxn];      // vis[i] 表示位置 i 是否被访问过

int bfs() {
    int now, Next;
    queue<int> q;    // BFS 队列
    q.push(n);       // 初始位置入队
    step[n] = 0;     // 初始步数为 0
    vis[n] = true;   // 标记已访问

    while (!q.empty()) {
        now = q.front();  // 取出队首元素
        q.pop();

        // 三种移动方式：X-1, X+1, 2*X
        for (int i = 0; i < 3; i++) {
            if (i == 0)
                Next = now - 1;
            else if (i == 1)
                Next = now + 1;
            else
                Next = now * 2;

            // 检查是否越界或已访问
            if (Next < 0 || Next >= maxn) continue;
            if (!vis[Next]) {
                step[Next] = step[now] + 1;  // 更新步数
                q.push(Next);                // 新位置入队
                vis[Next] = true;            // 标记已访问
            }

            // 如果到达目标位置，直接返回步数
            if (Next == k) return step[Next];
        }
    }
    return -1;  // 理论上不会执行，因为题目保证有解
}

int main() {
    memset(vis, false, sizeof(vis));  // 初始化 vis 数组
    memset(step, 0, sizeof(step));   // 初始化 step 数组
    scanf("%d %d", &n, &k);          // 输入 N 和 K
    ans = bfs();                     // 执行 BFS
    printf("%d\n", ans);             // 输出答案
    return 0;
}

关键点总结

1. BFS 队列：用于按层遍历所有可能的移动方式。
2. 步数记录：step 数组记录到达每个点的最少时间。
3. 剪枝优化：
   • 限制 X 在 [0, 1e5] 范围内。
   • 避免重复访问（vis 数组）。
4. 时间复杂度：最坏情况是 O(1e5)，因为每个点最多访问一次。

这个解法保证了在最短时间内找到答案，适用于题目给定的数据范围。