首页 > 代码库 > HDU2717BFS

HDU2717BFS

/*
	WA了12发简直不能忍!

。 题意非常简单。从正整数a变为b有三种方法: +1,-1。*2 特殊情况一:a与b相等不须要搜索 特殊情况二:a>b时。结果必定是a-b不需搜 特殊情况三:比較坑!

。!

当 a 与 b 区别较大的时候。若一直依照三种方法产生子节点的话, 不断不断不断不断不断*2*2*2*2*2是非常easy超过数组长度的 并且当不断*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