【POJ 3278】Catch That Cow 题解（广度优先搜索）

农夫约翰已被告知一头逃亡奶牛的位置，并想立即抓住她。他从一条数字线上的N点（0≤N≤100000）开始，奶牛在同一条数字线上的K点（0≥K≤100000）。农夫约翰有两种交通方式：步行和坐车。 *步行：FJ可以在一分钟内从任何点X移动到点X-1或X+1 *坐车：FJ可以在一分钟内从任何X点移动到2×X点。 如果奶牛没有意识到它的追赶，根本不动，农夫约翰需要多长时间才能找回它？

输入 第1行：两个空格分隔的整数：N和K 输出 第1行：农夫约翰抓住逃跑的奶牛所需的时间最少，以分钟为单位。 样品

输入 5 17 输出 4.

暗示 农夫约翰到达逃亡奶牛的最快方式是沿着以下路径移动：5-10-9-18-17，需要4分钟。

思路

若k <= n，无法前进，则无法坐车，只能步行，直接输出（n - k）。若k > n，将起点入队，标记为已访问，步数为0。若队列非空，队首出队，判断是否是终点。如果是，则输出该点步数；如果不是，则拓展f + 1，f - 1，f * 2三个方向，判断无越界且未访问后入队，标记为已访问，步数加一。

AC代码

#include <iostream>
#include <queue>
#include <bitset>
using namespace std;
#define AUTHOR "HEX9CF"

const int maxn = 100005;

int n, k;
queue<int> q;
bitset<maxn> vis;
int stp[maxn];

void extend(int x, int f)
{
    if (x >= 0 && x <= 100000 && !vis[x])
    {
        vis[x] = 1;
        stp[x] = stp[f] + 1;
        q.push(x);
    }
}

void bfs()
{
    q.push(n);
    vis[n] = 1;
    stp[n] = 0;
    while (!q.empty())
    {
        int f;
        f = q.front();
        q.pop();
        if (k == f)
        {
            cout << stp[k] << endl;
            return;
        }
        extend(f + 1, f);
        extend(f - 1, f);
        extend(f * 2, f);
    }
}

int main()
{
    cin >> n >> k;
    if (k <= n)
    {
        cout << n - k << endl;
    }
    else
    {
        bfs();
    }
    return 0;
}