[USACO07OPEN]Catch That Cow

川长思鸟来 2021-09-29 14:50 230阅读 0赞

**题目：**洛谷P1588、HDU2717

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

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

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

两处题目读入不太一样。

细节见代码。

**C++ Code：**

1 #include<cstdio>
     2 #include<queue>
     3 #include<cstring>
     4 using namespace std;
     5 bool b[100051];
     6 int main(){
     7     int n,k;
     8     while(scanf("%d%d",&n,&k)!=EOF){
     9         if(n>=k){//特判n≥k的情况
    10             printf("%d\n",n-k);continue;
    11         }
    12         queue<int>q1,q2;
    13         q1.push(n);
    14         q2.push(0);
    15         memset(b,1,sizeof(b));
    16         b[n]=0;
    17         while(!q1.empty()){
    18             int p=q1.front();q1.pop();
    19             int P=q2.front();q2.pop();
    20             int l=p-1;
    21             if(l&&b[l]){
    22                 if(l==k){
    23                     printf("%d\n",P+1);break;
    24                 }
    25                 b[l]=0;
    26                 q1.push(l);
    27                 q2.push(P+1);
    28             }
    29             l=p+1;
    30             if(l<=100000&&b[l]){
    31                 if(l==k){
    32                     printf("%d\n",P+1);break;
    33                 }
    34                 b[l]=0;
    35                 q1.push(l);
    36                 q2.push(P+1);
    37             }
    38             l=p*2;
    39             if(l<=100000&&b[l]){
    40                 if(l==k){
    41                     printf("%d\n",P+1);break;
    42                 }
    43                 b[l]=0;
    44                 q1.push(l);
    45                 q2.push(P+1);
    46             }
    47         }
    48     }
    49     return 0;
    50 }

转载于:https://www.cnblogs.com/Mrsrz/p/6921104.html