简答题
偏难
#7156
抓牛 农夫知道一头牛的位置,想要抓住它。农夫和牛都位于数轴上,农夫起始位于点N(0<=N<=100000),牛位于点K(0<=K<=100000)。农夫有两种移…
抓牛
农夫知道一头牛的位置,想要抓住它。农夫和牛都位于数轴上,农夫起始位于点N(0<=N<=100000),牛位于点K(0<=K<=100000)。农夫有两种移动方式:
1、从X移动到X-1或X+1,每次移动花费一分钟
2、从X移动到2*X,每次移动花费一分钟
假设牛没有意识到农夫的行动,站在原地不动。农夫最少要花多少时间才能抓住牛?
时间限制:2000
内存限制:65536
输入
两个整数,N和K
输出
一个整数,农夫抓到牛所要花费的最小分钟数
样例输入
5 17
样例输出
4
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <bits/stdc++.h>
using namespace std;
int b[200100];
int a[10];
queue<int> q;
int n, k;
void bfs(int x) {
q.push(x);
b[x] = 1;
while (!q.empty()) {
int s = q.front();
a[1] = s - 1;
a[2] = s + 1;
a[3] = 2 * s;
for (int i = 1; i < 4; i++) {
if (b[a[i]] == 0 && a[i] >= 0 && a[i] < 100100) {
b[a[i]] = b[s] + 1;
q.push(a[i]);
if (a[i] == k) {
cout << b[k] - 1 << endl;
}
}
}
q.pop();
}
}
int main() {
cin >> n >> k;
bfs(n);
return 0;
}</pre>
这道题暂未补解析。