首页 > 代码库 > POJ 3278 Catch That Cow BFS
POJ 3278 Catch That Cow BFS
1.题意:给定两个数N,K,N表示初始状态,K表示目标状态,有三种操作:+1,-1和*2,试求这个过程的最少的操作次数;
2.输入输出:依次给出N,K;
3.分析:典型的BFS求最小操作数,唯一注意的就是搜索过程中注意状态值不要超出K的范围:[0,1e5];
1 # include <iostream> 2 # include <cstdio> 3 # include <queue> 4 using namespace std; 5 const int maxn=1e5+10; 6 int N,K; 7 int vis[maxn]; 8 struct Node 9 { 10 int X,T; 11 Node(){} 12 Node(int x,int t) 13 { 14 X=x; 15 T=t; 16 } 17 }; 18 void Init() 19 { 20 for(int i=0;i<maxn;i++) 21 vis[i]=0; 22 vis[N]=1; 23 } 24 void Solve() 25 { 26 int ans=-1; 27 queue<Node> q; 28 q.push(Node(N,0)); 29 while(!q.empty()) 30 { 31 Node temp=q.front(); 32 q.pop(); 33 if(temp.X==K) 34 { 35 ans=temp.T; 36 break; 37 } 38 if(temp.X+1<maxn&&!vis[temp.X+1]) 39 { 40 vis[temp.X+1]=1; 41 q.push(Node(temp.X+1,temp.T+1)); 42 } 43 if(temp.X-1>=0&&!vis[temp.X-1]) 44 { 45 vis[temp.X-1]=1; 46 q.push(Node(temp.X-1,temp.T+1)); 47 } 48 if(temp.X*2<maxn&&!vis[temp.X*2]) 49 { 50 vis[temp.X*2]=1; 51 q.push(Node(temp.X*2,temp.T+1)); 52 } 53 } 54 printf("%d\n",ans); 55 } 56 int main() 57 { 58 while(scanf("%d%d",&N,&K)!=EOF) 59 { 60 Init(); 61 Solve(); 62 } 63 return 0; 64 }
POJ 3278 Catch That Cow BFS
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。