(bfs)解答

Vjudge

A - Catch That Cow

这道经典的追牛问题设定在一条无限延伸的数轴上。John 起始于位置 n，而静止不动的奶牛位于位置 k。John 拥有三种移动策略：向左移动一格（x-1）、向右移动一格（x+1）或者瞬间传送至当前位置的两倍（2x）。我们的目标是计算 John 到达奶牛位置所需的最少步数。

首先，我们需要对边界情况进行特殊处理，以优化算法效率。当 n \ge k 时，由于传送操作 2x 会使位置迅速远离目标（除非 x=0，但通常 n,k 为正整数），且向左移动是唯一的缩短距离的方式，因此 John 只能逐步后退，所需步数即为 n-k。若 n=k，步数为 0，这可以视为上述情况的一个特例。

当 n < k 时，问题转化为在状态空间中寻找最短路径。由于传送操作具有指数级增长的特性，盲目搜索会导致状态空间爆炸。因此，采用广度优先搜索（BFS）是解决此类最短路径问题的标准且高效的方法。BFS 能够保证第一次访问到目标节点时的路径长度即为最短路径。在搜索过程中，我们需要维护一个队列来存储当前层的所有状态，并配合一个访问标记数组（或哈希表）来避免重复访问同一位置，从而确保算法的线性时间复杂度。

``