[USACO07OPEN]Catch That Cow

题目：洛谷P1588、HDU2717

题目大意：有一个人在点$n$，一头牛在点$k$，人每秒能从$x$移动到点$x+1$、$x-1$、$2x$，牛不会动，求最少多少秒后人能移动到牛所在的$k$。

思路：BFS。按照题意进行广搜。

注意：题目数据较大，如中途计算中的点$x$大于100000或小于1，则不放入队列中。

两处题目读入不太一样。

细节见代码。

C++ Code：

 #include<cstdio>

 #include<queue>

 #include<cstring>

 using namespace std;

 bool b[];

 int main(){

     int n,k;

     while(scanf("%d%d",&n,&k)!=EOF){

         if(n>=k){//特判n≥k的情况

             printf("%d\n",n-k);continue;

         }

         queue<int>q1,q2;

         q1.push(n);

         q2.push();

         memset(b,,sizeof(b));

         b[n]=;

         while(!q1.empty()){

             int p=q1.front();q1.pop();

             int P=q2.front();q2.pop();

             int l=p-;

             if(l&&b[l]){

                 if(l==k){

                     printf("%d\n",P+);break;

                 }

                 b[l]=;

                 q1.push(l);

                 q2.push(P+);

             }

             l=p+;

             if(l<=&&b[l]){

                 if(l==k){

                     printf("%d\n",P+);break;

                 }

                 b[l]=;

                 q1.push(l);

                 q2.push(P+);

             }

             l=p*;

             if(l<=&&b[l]){

                 if(l==k){

                     printf("%d\n",P+);break;

                 }

                 b[l]=;

                 q1.push(l);

                 q2.push(P+);

             }

         }

     }

     return ;

 }

巴特西

[USACO07OPEN]Catch That Cow

最新文章

热门文章