首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。