#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int Max = 100000 + 10;
int vis[Max];
int t[Max]; //记录时间
int n,k; 

void bfs()
{
	int now,temp;
	queue<int> q;
	q.push(n);
	while(!q.empty())
	{
		now = q.front();
		q.pop();
		if(now == k)
		{
			cout<<t[now]<<endl;
			return;
		}
		
		for(int i=1; i<=3; i++)
		{
			if(i == 1)
			{
				temp = now + 1;
			}
			if(i == 2)
			{
				temp = now - 1;
			}
			if(i == 3)
			{
				temp = now * 2;
			}
			if(!vis[temp] && temp >= 0 && temp < Max)
			{
				vis[temp] = 1;
				t[temp] = t[now] + 1;
				q.push(temp);
			}
		}
	}
}
		
int main()
{
	while(scanf("%d %d",&n,&k) != EOF)
	{
		memset(vis, 0, sizeof(vis));
		bfs();
	}
	return 0;
}
		

• Re:水题~最基础的BFS (919) 13408229 2014-08-09 10:52:28