POJ 3278 Catch That Cow（BFS）

题目链接：点击这里

BFS入门题

分为两种情况：

1. 一个是 n>=k 就只能每次向后退一步，最少步数就是两数的差
2. 另一种是 n<=k 的情况，BFS，满足范围即入队列，对当前的坐标进行标记，步数加1，到达目标点返回结果。

第一种情况包含于第二种，因此，广搜即可。

#include<iostream>
#include<algorithm>
#include<string>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<stack>
#include<queue>
#include<map>

using namespace std;
typedef long long ll;
const int MOD = 10000007;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
const int maxn = 100010;
bool inq[maxn] = {false};
map<int,int> mp;
int n, k;

bool judge(int x)
{
	if(x<0||x>100000)	return false;
	if(inq[x]==true)	return false;
	return true;
}


int BFS()
{
	queue<int> q;
	q.push(n);
	inq[n] = true;	//已入队 
	mp[n] = 0;
	while(!q.empty())
	{
		int top = q.front();
		q.pop();
		if(top==k)
			return mp[top];
		
		if(judge(top+1))
		{
			q.push(top+1);
			inq[top+1] = true;
			mp[top+1] = mp[top]+1; 
		}
		if(judge(top-1))
		{
			q.push(top-1);
			inq[top-1] = true;
			mp[top-1] = mp[top]+1; 
		}
		if(judge(top*2))
		{
			q.push(top*2);
			inq[top*2] = true;
			mp[top*2] = mp[top]+1; 
		}
	}
}

int main()
{
	cin>>n>>k;
	cout<<BFS()<<endl;
	return 0;
}