广度优先搜索算法-找牛

洛谷：P1588
OJ平台：T1253

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

代码实现：BFS

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/****************************************************************
 * 代码作者: Alex Li
 * 创建时间: 2026-04-22
 * 文件描述: CYOJ T1253 用 BFS 方法找牛，生成新位置时判断 target
****************************************************************/

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

const int MAX_POS = 100000;

struct Node {
    int position;
    int time;
};

bool isValidPosition(int position) {
    return position >= 0 && position <= MAX_POS;
}

int catchCow(int start, int target) {
    if (start >= target) {
        return start - target;
    }

    vector<bool> visited(MAX_POS + 1, false);
    queue<Node> q;

    q.push({start, 0});
    visited[start] = true;

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

        int nextTime = current.time + 1;
        int nextPositions[3] = {
            current.position - 1,
            current.position + 1,
            current.position * 2
        };

        for (int i = 0; i < 3; i++) {
            int nextPosition = nextPositions[i];

            if (!isValidPosition(nextPosition) || visited[nextPosition]) {
                continue;
            }

            if (nextPosition == target) {
                return nextTime;
            }

            visited[nextPosition] = true;
            q.push({nextPosition, nextTime});
        }
    }

    return -1;
}

int main() {
    int start, target;
    cin >> start >> target;

    cout << catchCow(start, target) << endl;

    return 0;
}
Previous Topic
Back to Lesson
Next Topic