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 
#include 
#include 
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<