C. [202506C]抓住那头牛 2
文件操作
时间限制: 1000ms
空间限制: 262144KB
输入文件名: 202506C.in
输出文件名: 202506C.out
Time Limit Exceeded
10 分
题目描述
在一个数轴上，农夫约翰在点 AA，他的一头奶牛在点 BB。农夫约翰想要尽快抓住那头牛。
农夫约翰有两种移动方式：走路和传送。
- 走路：花一分钟从点 XX 移动到点 X+1X+1 或点 X−1X−1
- 传送：花一分钟从点 XX 移动到点 2X2X
牛不知道农夫约翰在抓它，在点 BB 一动不动。
农夫约翰最少要花多少分钟才能抓到那头牛？
输入格式
AA BB
输出格式
输出一个整数，表示农夫约翰最少要花多少分钟才能抓到那头牛。
样例
Input 1
5 17
Output 1
4
数据范围
- 0≤A,B≤10180≤A,B≤1018
- A,BA,B 都是整数
样例解释
农夫约翰一开始点 55，奶牛在点 1717。
农夫约翰到达牛所在的位置的最快方法是 5→10→9→18→175→10→9→18→17，需要 44 分钟。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a, b;
map<int, bool> vis;
struct node {
int num;
int step;
};
void bfs() {
queue<node> q;
q.push(node {a, 0});
vis[a] = 1;
while (!q.empty()) {
node now = q.front();
q.pop();
if (now.num == b) {
cout << now.step << "\n";
return;
}
int next = now.num + 1;
if (next <= 2 * b && !vis[next]) {
vis[next] = 1;
q.push({next, now.step + 1});
}
next = now.num - 1;
if (next >= 0 && !vis[next]) {
vis[next] = 1;
q.push({next, now.step + 1});
}
next = now.num * 2;
if (next <= 2 * b && !vis[next]) {
vis[next] = 1;
q.push({next, now.step + 1});
}
}
}
signed main() {
freopen("202506C.in", "r", stdin);
freopen("202506C.out", "w", stdout);
cin >> a >> b;
if (b <= a) {
cout << a - b << "\n";
return 0;
}
bfs();
return 0;
}
