信息学奥赛一本通 1253：抓住那头牛 广度优先搜索算法
农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点N(0≤N≤100000)，牛位于点K(0≤K≤100000)。假设牛没有意识到农夫的行动，站在原地不动。农夫最少要花多少时间才能抓住牛？时间限制: 1000 ms内存限制: 65536 KB。1、从X移动到X−1或X+1，每次移动花费一分钟。一个整数，农夫抓到牛所要花费的最小分钟数。2、从X移动到2×X，每次移动花费一分钟。1
·
1253：抓住那头牛
时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点N(0≤N≤100000)，牛位于点K(0≤K≤100000)。农夫有两种移动方式：
1、从X移动到X−1或X+1，每次移动花费一分钟
2、从X移动到2×X，每次移动花费一分钟
假设牛没有意识到农夫的行动，站在原地不动。农夫最少要花多少时间才能抓住牛？
【输入】
两个整数，N和K。
【输出】
一个整数，农夫抓到牛所要花费的最小分钟数。
【输入样例】
5 17
【输出样例】
4
#include<bits/stdc++.h>
using namespace std;
int n,k;
bool b[2000005];
queue <int> qx;
queue <int> qs;
int main() {
cin>>n>>k;
qx.push(n);
qs.push(0);
while(!qx.empty()){
int x=qx.front();
int s=qs.front();
if (x==k){
cout<<s;
return 0;
}
qx.pop();
qs.pop();
if (b[x+1]==0){
qx.push(x+1);
qs.push(s+1);
b[x+1]=1;
}
if (x-1>=0&&b[x-1]==0){
qx.push(x-1);
qs.push(s+1);
b[x-1]=1;
}
if (x*2<=200000&&b[x*2]==0){
qx.push(x*2);
qs.push(s+1);
b[x*2]=1;
}
}
return 0;
}
技术共进，成长同行——讯飞AI开发者社区
更多推荐
7
0- 0
已为社区贡献4条内容
所有评论(0)