1253:抓住那头牛
程序员文章站
2022-06-12 09:21:53
...
【题目描述】
农夫知道一头牛的位置,想要抓住它。农夫和牛都位于数轴上,农夫起始位于点N(0≤N≤100000),牛位于点K(0≤K≤100000)。农夫有两种移动方式:
1、从X移动到X−1或X+1,每次移动花费一分钟
2、从X移动到2×X,每次移动花费一分钟
假设牛没有意识到农夫的行动,站在原地不动。农夫最少要花多少时间才能抓住牛?
【输入】
两个整数,N和K。
【输出】
一个整数,农夫抓到牛所要花费的最小分钟数。
【输入样例】
5 17
【输出样例】
4
这是一道广搜题,一开始就没有什么思路。后来画了一个树状图,从起点出发,画出能到达的相邻点,一看这个图,瞬间就明白了用广搜来做(从起点2→终点7的图)。
代码如下:
#include<bits/stdc++.h>
using namespace std;
int N, A, B, vis[100005];
struct node{
int x, minn;
node(){//构造的空函数,需要的时候拿去用
}
node(int xx, int mmin){//构造函数(与node结构体变量类型与数量保持一致),这样避免一个一个的赋值
x = xx;
minn = mmin;
}
};
bool in(int x){
return x>=0 && x<=100005;//****x<=100005
}
void bfs(int x){
queue<node>q;//定义结构体类型的队列
q.push(node(x, 0));//放入元素:与构造函数变量类型、数量保持一致
vis[x] = 1;//访问过
while(!q.empty()){//队列不为空(empty()为空,返回true)
node now = q.front();//返回头部元素:存储在结构体中
q.pop();//弹出元素
if(now.x == B){//目标结点:输出并退出
cout << now.minn;
return ;
}
for(int i=0; i<3; i++){//访问相邻结点
int tx;
if(i == 0)
tx = now.x + 1;
else if(i == 1)
tx = now.x - 1;
else
tx = now.x * 2;
if(in(tx) && vis[tx] == 0){//该点未被访问过且合法:把新结点存入队尾
vis[tx] = true;
q.push(node(tx, now.minn+1));
}
}
}
}
int main(){
cin >> A >> B;
bfs(A);
return 0;
}
上一篇: 使用Cmder替换cmd,让开发更高效
下一篇: 抓住那头牛「题解」