Catch That Cow_C/C++_编程开发_程序员俱乐部

class="pst" style="">Description

Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point?N?(0 ≤?N?≤ 100,000) on a number line and the cow is at a point?K?(0 ≤?K?≤ 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting.

* Walking: FJ can move from any point?X?to the points?X?- 1 or?X?+ 1 in a single minute
* Teleporting: FJ can move from any point?X?to the point 2 ×?X?in a single minute.

If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?

Input

Line 1: Two space-separated integers:?N?and?K

Output

Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.

Sample Input

5 17

Sample Output

4

Hint

The fastest way for Farmer John to reach the fugitive cow is to move along the following path: 5-10-9-18-17, which takes 4 minutes.

#include"iostream"
#include"queue"

using namespace std;

#define MAX 100000

int dis[MAX + 1];
bool check[MAX + 1];

int catch_Cow(int n, int k) {
	int c;
	queue<int> q;
	q.push(n);
	dis[n] = 0;
	check[n] = 1;
	while(!q.empty()) {
		c = q.front();
		q.pop();
		if(c - 1 >= 0 && c - 1 < MAX + 1 && !check[c - 1]) {
			check[c - 1] = 1;
			dis[c - 1] = dis[c] + 1;
			q.push(c - 1);
		}
		if(c + 1 >= 0 && c + 1 < MAX + 1 && !check[c + 1]) {
			check[c + 1] = 1;
			dis[c + 1] = dis[c] + 1;
			q.push(c + 1);
		}
		if(c * 2 >= 0 && c * 2 < MAX + 1 && !check[c * 2]) {
			check[c * 2] = 1;
			dis[c * 2] = dis[c] + 1;
			q.push(c * 2);
		}
		if(c == k) 
			return dis[c];
	}
	return 0;
}

int main() {
	int john_n, cow_k;
	while (cin>>john_n>>cow_k) {
		memset(check,0,sizeof(check));
		memset(dis,0,sizeof(dis));
		cout<<catch_Cow(john_n, cow_k)<<endl<<endl;
	}
	return 0;
}