NOI 2971 抓住那头牛

标题

抓住那头牛

详情

农民约翰的农场有一头逃亡了。现在已知的牛的位置并立即想抓住她。约翰从的起始点为S,牛目前在点K。农民约翰有两种行进方式:步行和传送。
步行:约翰可以从任何点X, 走到X-1或 X+1,耗时一分钟。
传送:约翰可以从任何点的X,传送到点2X,耗时一分钟。

输入格式

只有一行包含两个整数S和K

输出格式

输出一个整数,表示农民约翰需要在几分钟内抓逃犯牛。

限制

0<=S<=100000
0<=K<=100000

样例

  • 输入 5 17

  • 输出 4

  • 解释 农民约翰的最快的方式到达逃亡的位置式沿着以下路径:5-10-9-18-17,需要4分钟。

思路

从农民约翰的起点出发,采用广度优先搜索,注意将点的坐标限制在给定的范围内。同时,可以使用一个整型数组来记录某个点是否已经被访问过,如果被访问过了则记录到达该点需要的时间。

代码

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

int main() {
    int* flag = new int[100001]();
    for (int i = 1; i < 100001; i++) {
        flag[i] = -1;
    }
    int S, K;
    cin >> S >> K;
    flag[S] = 0;
    queue<int> q;
    q.push(S);
    int f;

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

        if (f == K) {
            break;
        }

        int a[3] = { f + 1, f - 1,  f * 2 };        
        for (int i = 0; i < 3; i++) {
            if (a[i] > 0 && a[i] < 100001 && flag[a[i]] == -1) {
                flag[a[i]] = flag[f] + 1;
                q.push(a[i]);
            }
        }
    }

    cout << flag[f];
}

分享