简答题
偏难
#7471
抓牛(2023.12) 农夫知道一头牛的位置,想要抓住它。农夫和牛都位于数轴上,农夫起始位于点N(0<=N<=100000),牛位于点K(0<=K<=10000…
抓牛(2023.12)
农夫知道一头牛的位置,想要抓住它。农夫和牛都位于数轴上,农夫起始位于点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">// 参考代码1
#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><pre class="brush:cpp;toolbar:false">// 参考代码2
#include <bits/stdc++.h>
using namespace std;
int n, k;
bool v[100005];
struct nod {
int x, dis;
};
int main() {
cin >> n >> k;
queue<nod> q;
if (n == k) {
cout << 0;
return 0;
}
v[n] = true;
q.push({n, 0});
while (!q.empty()) {
int l = q.size();
for (int i = 1; i <= l; i++) {
if (q.front().x + 1 == k || q.front().x - 1 == k ||
q.front().x * 2 == k) {
cout << q.front().dis + 1;
return 0;
}
if (q.front().x + 1 >= 0 && q.front().x + 1 <= 100000 &&
!v[q.front().x + 1]) {
v[q.front().x + 1] = true;
q.push({q.front().x + 1, q.front().dis + 1});
}
if (q.front().x - 1 >= 0 && q.front().x - 1 <= 100000 &&
!v[q.front().x - 1]) {
v[q.front().x - 1] = true;
q.push({q.front().x - 1, q.front().dis + 1});
}
if (q.front().x * 2 >= 0 && q.front().x * 2 <= 100000 &&
!v[q.front().x * 2]) {
v[q.front().x * 2] = true;
q.push({q.front().x * 2, q.front().dis + 1});
}
q.pop();
}
}
return 0;
}</pre>
这道题暂未补解析。