非常可乐 (BFS ➕ 模拟)

题目链接：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 }