欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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的图)。
1253:抓住那头牛
代码如下:

#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;
}
相关标签: 一本通 bfs