农夫抓牛：伪代码实现及时空性能分析

问题描述： 假设农夫和牛都位于数轴上，农夫位于点 N，牛位于点 K（K>N），农夫有以下两种移动方式：（1）从点 X 移动到 X-1 或 X+1，每次移动花费一分钟；（2）从点 X 移动到点 2X，每次移动花费一分钟。假设牛没有意识到农夫的行动，站在原地不动，农夫最少要花费多长时间才能抓住牛？

伪代码描述：

# 初始化农夫的位置 N 和牛的位置 K
N = ...
K = ...

# 初始化一个队列 queue，用于保存农夫的位置和已花费的时间，初始值为 (N, 0)
queue = [(N, 0)]

# 初始化一个集合 visited，用于保存已经访问过的位置，初始值为包含农夫的位置 N
visited = {N}

# 循环直到队列为空
while queue:
    # 弹出队列的第一个元素 (curPos, curTime)
    curPos, curTime = queue.pop(0)

    # 如果当前位置为牛的位置 K，则返回当前已花费的时间 curTime
    if curPos == K:
        return curTime

    # 如果当前位置的 2 倍没有被访问过且在数轴范围内，则将其加入队列，并更新已花费的时间为 curTime + 1
    if 2 * curPos not in visited and 2 * curPos >= 0:
        queue.append((2 * curPos, curTime + 1))
        visited.add(2 * curPos)

    # 如果当前位置的前一步没有被访问过且在数轴范围内，则将其加入队列，并更新已花费的时间为 curTime + 1
    if curPos - 1 not in visited and curPos - 1 >= 0:
        queue.append((curPos - 1, curTime + 1))
        visited.add(curPos - 1)

    # 如果当前位置的后一步没有被访问过且在数轴范围内，则将其加入队列，并更新已花费的时间为 curTime + 1
    if curPos + 1 not in visited:
        queue.append((curPos + 1, curTime + 1))
        visited.add(curPos + 1)

# 如果循环结束时仍未找到牛的位置，则返回 -1（表示无法抓住牛）
return -1

时空性能分析：

**时间复杂度：**最坏情况下，农夫需要遍历所有可能的位置才能抓住牛，而每个位置可以有两个移动方式，因此时间复杂度为 O(2^N)，其中 N 是牛的位置与农夫的位置之差。
**空间复杂度：**空间复杂度主要由队列和集合占用。队列的大小最坏情况下为 O(2^N)，集合的大小最坏情况下也为 O(2^N)，因此空间复杂度为 O(2^N)。