首页 > 代码库 > HDU2717BFS

HDU2717BFS

/*
	WA了12发简直不能忍!!
	
	题意很简单,从正整数a变为b有三种方法:
	+1,-1,*2
	
	特殊情况一:a与b相等不需要搜索
	特殊情况二:a>b时,结果必然是a-b不需搜 
	特殊情况三:比较坑!!!
		当 a 与 b 差别较大的时候,若一直按照三种方法产生子节点的话,
			不断不断不断不断不断*2*2*2*2*2是很容易超过数组长度的
			而且当不断*2超过k之后,再次产生的新节点并没有意义,所以产生*2类型的新节点时要加判断条件
	
	希望自己能够长记性
	大家也能一起加油 
*/ 

#include <iostream>
#include <cstdio>
#include <string>
using namespace std;

#define MAXN 200000

int main() 
{
	int que[MAXN];
	int book[MAXN];
	int i,j,k,m,n,head,tail,new_pos;
	while(cin>>n>>k)
	{
		memset(book,0,sizeof(book));
		if (n==k)
		{
			printf("0\n");
			continue;
		}
		if (n>k)
		{
			printf("%d\n",n-k);
			continue;
		}
		head=tail=1;
		que[head]=n;
		while(!book[k]&&head<=tail)
		{
			new_pos=que[head]+1;
			if (!book[new_pos])
				que[++tail]=new_pos,book[new_pos]=book[que[head]]+1;
			new_pos=que[head]-1;
			if (!book[new_pos])
				que[++tail]=new_pos,book[new_pos]=book[que[head]]+1;
			new_pos=que[head]*2;
			if (!book[new_pos]&&new_pos<=2*k)//这句话的后半句是精髓,试了很多很多次! 
				que[++tail]=new_pos,book[new_pos]=book[que[head]]+1;
			head++;
		}
		cout<<book[k]<<endl;
	}
	return 0;
}

HDU2717BFS