题目链接：https://ac.nowcoder.com/acm/contest/984/L/
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 <= N <= 100,000) on a number line and the cow is at a point K (0 <= K <= 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting.
Walking: FJ can move from any point X to the points X-1 or X+1 in a single minute Teleporting: FJ can move from any point X to the point 2*X in a single minute.
If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?

输入描述

Line 1: Two space-separated integers: N and K

输出描述

Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.

输入

5 17

输出

4

说明

Farmer John starts at point 5 and the fugitive cow is at point 17.
The fastest way for Farmer John to reach the fugitive cow is to move along the following path: 5-10-9-18-17, which takes 4 minutes.

解题思路

题意:从s到t，可加1，可减1，可乘2，问多少步能到达。
思路:BFS。

Accepted Code:

#include <bits/stdc++.h>
using namespace std;
struct edge {
    int x, l;
}u;
int vis[100005], arr[2] = {1, -1};
int BFS(int s, int t) {
    int tx;
    vis[s] = 1;
    queue <edge> Q;
    Q.push((edge){s, 0});
    while (!Q.empty()) {
        u = Q.front();
        Q.pop();
        if (!(u.x - t))
            return u.l;
        for (int i = 0; i < 3; i++) {
            if (!i)
                tx = u.x << 1;
            else tx = u.x + arr[i - 1];
            if (tx < 0 || tx > 100000 || vis[tx])
                continue;
            Q.push((edge){tx, u.l + 1});
            vis[tx] = 1;
        }
    }
    return -1;
}
int main() {
    int s, t;
    scanf("%d%d", &s, &t);
    printf("%d\n", BFS(s, t));
    return 0;
}