一本通-1253：抓住那头牛（一维BFS）

【题目描述】 农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点N(0≤N≤100000)，牛位于点K(0≤K≤100000)。农夫有两种移动方式：

1、从X移动到X-1或X+1，每次移动花费一分钟

2、从X移动到2*X，每次移动花费一分钟

假设牛没有意识到农夫的行动，站在原地不动。农夫最少要花多少时间才能抓住牛？

【输入】 两个整数，N和K。

【输出】 一个整数，农夫抓到牛所要花费的最小分钟数。

【输入样例】 5 17

【输出样例】 4

---

#include <bits/stdc++.h>

using namespace std;

vector<int> path(1e5 + 5, INT_MAX);

int start, end;

void BFS()
{
    path[start] = 0;
    queue<int> q;
    q.push(start);

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

        if (tmp == end) break;

        for (int i = 0; i < 3; ++i) {
            int nextPos;
            switch(i) {
                case 0: nextPos = tmp + 1; break;
                case 1: nextPos = tmp - 1; break;
                default: nextPos = (tmp << 1);
            }

            if (0 <= nextPos && nextPos <= 1e5 && path[nextPos] > path[tmp] + 1) {
                path[nextPos] = path[tmp] + 1;
                q.push(nextPos);
            }
        }
    }

    cout << path[end];
}



int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> start >> end;
    BFS();

    return 0;
}