首页 > 代码库 > BFS/poj 3278 Catch That Cow

BFS/poj 3278 Catch That Cow

 1 #include<cstdio> 2 #include<queue> 3 #include<cstring> 4 using namespace std; 5 const int MAXN=200010; 6 int n,k; 7 bool v[MAXN]; 8 struct point 9 {10     int x;11     int step;12 };13 int bfs()14 {15     memset(v,0,sizeof(v));16     queue<point>que;17     point now,next;18     now.x=n;19     now.step=0;20     v[n]=1;21     que.push(now);22 23     while (!que.empty())24     {25         now=que.front();26         que.pop();27         if (now.x==k) break;28 29         next.x=now.x+1;30         if (next.x>=0 && next.x<=MAXN && !v[next.x])31         {32             v[next.x]=1;33             next.step=now.step+1;34             que.push(next);35         }36 37         next.x=now.x-1;38         if (next.x>=0 && next.x<=MAXN && !v[next.x])39         {40             v[next.x]=1;41             next.step=now.step+1;42             que.push(next);43         }44 45         next.x=now.x*2;46         if (next.x>=0 && next.x<=MAXN && !v[next.x])47         {48             v[next.x]=1;49             next.step=now.step+1;50             que.push(next);51         }52 53     }54     return now.step;55 }56 57 int main()58 {59     while (scanf("%d%d",&n,&k)!=EOF)60     {61         printf("%d\n",bfs());62     }63     return 0;64 }

 

BFS/poj 3278 Catch That Cow