非常可乐 (BFS ➕ 模拟)

ゞ浴缸里的玫瑰 2021-12-03 23:23 214阅读 0赞

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=1495][http_acm.hdu.edu.cn_showproblem.php_pid_1495]

题目大意：

给你两个杯子还有一瓶可乐，问你可不可以通过杯子以及可乐之间互相倒来倒去 使最后两个人喝到相同的可乐，注意杯子没有刻度

思路：

这道题很像曾经做过的小学题目，我们不妨把所有情况都列举出来

a->b  a->c

b->a  b->c

c->a  c->b

总共就是六种情况，然后针对不同的情况不同的讨论。具体的细节实现还是看代码吧

1 #include <iostream>
      2 #include <string>
      3 #include <cstring>
      4 #include <queue>
      5 #include <string.h>
      6 #include <stdio.h>
      7 #include <vector>
      8 
      9 using namespace std;
     10 
     11 int vist[105][105][105],a,b,c;
     12 struct node
     13 {
     14     int a,b,c;
     15     int step;
     16 }s[105];
     17 int sum=0;
     18 void bfs()
     19 {
     20     queue<node>q;
     21     memset(vist,0,sizeof(vist));
     22     node p1;
     23     p1.a=a;
     24     p1.b=0;
     25     p1.c=0;
     26     p1.step=0;
     27     q.push(p1);
     28     vist[p1.a][0][0]=1;
     29     while(!q.empty())
     30     {
     31         p1=q.front();
     32         q.pop();
     33         if((p1.a==a/2&&p1.b==a/2)||(p1.a==a/2&&p1.c==a/2)||(p1.b==a/2&&p1.c==a/2))
     34         {
     35             printf("%d\n",p1.step);
     36             return;
     37         }
     38         node p2;
     39         if(p1.a!=0)
     40         {
     41             if(p1.a>b-p1.b)
     42             {
     43                 p2.a=p1.a-(b-p1.b);
     44                 p2.b=b;
     45                 p2.c=p1.c;
     46                 p2.step=p1.step+1;
     47             }
     48             else
     49             {
     50                 p2.a=0;
     51                 p2.b=p1.b+p1.a;
     52                 p2.c=p1.c;
     53                 p2.step=p1.step+1;
     54             }
     55             if(!vist[p2.a][p2.b][p2.c])
     56             {
     57                 vist[p2.a][p2.b][p2.c]=1;
     58                 q.push(p2);
     59             }
     60         }
     61 
     62         if(p1.a!=0)
     63         {
     64             if(p1.a>c-p1.c)
     65             {
     66                 p2.a=p1.a-(c-p1.c);
     67                 p2.b=p1.b;
     68                 p2.c=c;
     69                 p2.step=p1.step+1;
     70             }
     71             else
     72             {
     73                 p2.a=0;
     74                 p2.b=p1.b;
     75                 p2.c=p1.c+p1.a;
     76                 p2.step=p1.step+1;
     77             }
     78             if(!vist[p2.a][p2.b][p2.c])
     79             {
     80                 vist[p2.a][p2.b][p2.c]=1;
     81                 q.push(p2);
     82             }
     83         }
     84 
     85         if(p1.b!=0)
     86         {
     87             if(p1.b>a-p1.a)
     88             {
     89                 p2.b=p1.b-(a-p1.a);
     90                 p2.a=a;
     91                 p2.c=p1.c;
     92                 p2.step=p1.step+1;
     93             }
     94             else
     95             {
     96                 p2.b=0;
     97                 p2.a=p1.a+p1.b;
     98                 p2.c=p1.c;
     99                 p2.step=p1.step+1;
    100             }
    101             if(!vist[p2.a][p2.b][p2.c])
    102             {
    103                 vist[p2.a][p2.b][p2.c]=1;
    104                 q.push(p2);
    105             }
    106         }
    107 
    108         if(p1.b!=0)
    109         {
    110             if(p1.b>c-p1.c)
    111             {
    112                 p2.b=p1.b-(c-p1.c);
    113                 p2.a=p1.a;
    114                 p2.c=c;
    115                 p2.step=p1.step+1;
    116             }
    117             else
    118             {
    119                 p2.b=0;
    120                 p2.a=p1.a;
    121                 p2.c=p1.c+p1.b;
    122                 p2.step=p1.step+1;
    123             }
    124             if(!vist[p2.a][p2.b][p2.c])
    125             {
    126                 vist[p2.a][p2.b][p2.c]=1;
    127                 q.push(p2);
    128             }
    129         }
    130 
    131         if(p1.c!=0)
    132         {
    133             if(p1.c>a-p1.a)
    134             {
    135                 p2.c=p1.c-(a-p1.a);
    136                 p2.a=a;
    137                 p2.b=p1.b;
    138                 p2.step=p1.step+1;
    139             }
    140             else
    141             {
    142                 p2.c=0;
    143                 p2.a=p1.a+p1.c;
    144                 p2.b=p1.b;
    145                 p2.step=p1.step+1;
    146             }
    147             if(!vist[p2.a][p2.b][p2.c])
    148             {
    149                 vist[p2.a][p2.b][p2.c]=1;
    150                 q.push(p2);
    151             }
    152         }
    153 
    154         if(p1.c!=0)
    155         {
    156             if(p1.c>b-p1.b)
    157             {
    158                 p2.c=p1.c-(b-p1.b);
    159                 p2.a=p1.a;
    160                 p2.b=b;
    161                 p2.step=p1.step+1;
    162             }
    163             else
    164             {
    165                 p2.c=0;
    166                 p2.a=p1.a;
    167                 p2.b=p1.b+p1.c;
    168                 p2.step=p1.step+1;
    169             }
    170             if(!vist[p2.a][p2.b][p2.c])
    171             {
    172                 vist[p2.a][p2.b][p2.c]=1;
    173                 q.push(p2);
    174             }
    175         }
    176     }
    177     printf("NO\n");
    178 }
    179 int main()
    180 {
    181     while(scanf("%d%d%d",&a,&b,&c)>0&&(a+b+c))
    182     {
    183         if(a%2==1)
    184         {
    185             printf("NO\n");
    186             continue;
    187         }
    188         bfs();
    189     }
    190     return 0;
    191 }

转载于:https://www.cnblogs.com/-Ackerman/p/11197458.html

[http_acm.hdu.edu.cn_showproblem.php_pid_1495]: http://acm.hdu.edu.cn/showproblem.php?pid=1495