广度优先搜索算法-找牛

洛谷：P1588
OJ平台：T1253

农夫在数轴上的某一点x处，一头牛站在数轴上的另一点y处，每一分钟，农夫可以在三种动作中选择一种动作，向左走一步，向右走一步，跳到当前位置x的2x处。问农夫最少需要几分钟，才能到达牛的位置抓住牛？

代码实现：BFS

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2024-12-30 18:00:32
 * 最后修改: 2024-12-30 18:21:49
 * 文件描述: 用BFS方法找牛
****************************************************************/

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

const int MAX_POS = 100000; // 最大范围

struct Node {
    int position; // 当前的位置
    int time;     // 从起点到当前位置所花费的时间
};

int catchCow(int start, int target) {
    if (start >= target) {
        return start - target; // 如果农夫已经在牛后面，只需要往回走
    }

    vector<bool> visited(MAX_POS + 1, false); // 用于标记是否访问过
    queue<Node> q; // BFS队列

    q.emplace({start, 0}); // 初始化，将起点加入队列
    visited[start] = true;

    while (!q.empty()) {
        Node current = q.front();
        q.pop();

        // 如果当前到达了目标位置，返回所需时间
        if (current.position == target) {
            return current.time;
        }

        // 尝试三种操作
        // 1. 向左走一步
        int newPosition = current.position - 1;
        if (newPosition >= 0 && !visited[newPosition]) {
            q.emplace({newPosition, current.time + 1});
            visited[newPosition] = true;
        }

        // 2. 向右走一步
        newPosition = current.position + 1;
        if (newPosition <= MAX_POS && !visited[newPosition]) {
            q.emplace({newPosition, current.time + 1});
            visited[newPosition] = true;
        }

        // 3. 跳跃到2倍位置
        newPosition = current.position * 2;
        if (newPosition <= MAX_POS && !visited[newPosition]) {
            q.emplace({newPosition, current.time + 1});
            visited[newPosition] = true;
        }
    }

    return -1; // 理论上不会到这里
}

int main() {
    int start, target;
    cout << "Enter farmer's position and cow's position: ";
    cin >> start >> target;

    int result = catchCow(start, target);
    cout << "Minimum time required: " << result << endl;

    return 0;
}

Previous Lesson

Back to Lesson

Next Topic

数据结构与算法

广度优先搜索算法-找牛