pku 3278 Catch That Cow 简单BFS

 1# include <iostream>
 2# include <cstring>
 3# include <queue>
 4# include <algorithm>
 5using namespace std;
 6int len[500001];
 7queue<int>q;
 8int main()
 9{
10    int n,k;
11    cin>>n>>k;
12    memset(len,-1,sizeof(len));
13    len[n]=0;
14    q.push(n);
15    while(!q.empty())
16    {
17      int top=q.front();
18      q.pop();
19      if(top==k)
20      {
21        cout<<len[k]<<endl;
22       // system("pause");
23        return 0;
24      }
25      if(top+1<=2*max(n,k)&&(len[top+1]==-1||len[top+1]>len[top]+1)) 
26      {
27              len[top+1]=len[top]+1;
28              q.push(top+1);
29      }
30      if(top-1>=0&&(len[top-1]==-1||len[top-1]>len[top]+1)) 
31      {
32              len[top-1]=len[top]+1;
33              q.push(top-1);
34      }
35      if(top<=max(n,k)&&(len[top*2]==-1||len[top*2]>len[top]+1))
36      {
37              len[top*2]=len[top]+1;
38              q.push(top*2);
39      }
40    }
41    return 0;
42}
43
44

posted on 2011-01-01 20:08 yzhw 阅读(183) 评论(0)  编辑 收藏 引用 所属分类: search


只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理


<2011年4月>
日一二三四五六
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

导航

统计

公告

统计系统

留言簿(1)

随笔分类(227)

文章分类(2)

OJ

最新随笔

搜索

积分与排名

最新评论

阅读排行榜