首页 > 代码库 > poj3278(bfs)
poj3278(bfs)
题目链接:http://poj.org/problem?id=3278
分析:广搜,每次三种情况枚举一下,太水不多说了。
#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <vector>#include <set>#include <map>#define LL long long#define mod 1000000007#define inf 0x3f3f3f3f#define N 100010using namespace std;struct node{ int x,step; bool operator<(const node a)const { return step>a.step; }};priority_queue<node>que;int vis[N];int judge(int x){ return x>=0&&x<=100000;}node make_node(int a,int b){ node temp; temp.x=a;temp.step=b; return temp;}int main(){ int n,k; while(scanf("%d%d",&n,&k)>0) { memset(vis,0,sizeof(vis)); while(!que.empty())que.pop(); que.push(make_node(n,0)); vis[n]=1; int ans=0; while(!que.empty()) { node now=que.top(); que.pop(); int x=now.x;//printf("%d %d\n",now.x,now.step); if(x==k) { ans=now.step; break; } if(judge(x+1)&&!vis[x+1]) { vis[x+1]=1;que.push(make_node(x+1,now.step+1)); } if(judge(x-1)&&!vis[x-1]) { vis[x-1]=1;que.push(make_node(x-1,now.step+1)); } if(judge(2*x)&&!vis[x*2]) { vis[x*2]=1;que.push(make_node(2*x,now.step+1)); } } printf("%d\n",ans); }}
poj3278(bfs)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。