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