031:非常可乐

Messj

Description
大家一定觉的运动以后喝可乐是一件很惬意的事情，但是seeyou却不这么认为。因为每次当seeyou买了可乐以后，阿牛就要求和seeyou一起分享这一瓶可乐，而且一定要喝的和seeyou一样多。但seeyou的手中只有两个杯子，它们的容量分别是N 毫升和M 毫升 可乐的体积为S （S<101）毫升　(正好装满一瓶) ，它们三个之间可以相互倒可乐 (都是没有刻度的，且 S==N+M，101＞S＞0，N＞0，M＞0) 。聪明的ACMER你们说他们能平分吗？如果能请输出倒可乐的最少的次数，如果不能输出"NO"。

Input
三个整数 : S 可乐的体积 , N 和 M是两个杯子的容量，以"0 0 0"结束。

Output
如果能平分的话请输出最少要倒的次数，否则输出"NO"。

Sample Input
7 4 3
4 1 3
0 0 0

Sample Output
NO
3

Messj

首先要深刻理解BFS，它不止用于地图，迷宫的问题。像这种求状态转移最快的步数或步骤的，就可以用BFS。这题也可以用广搜，以后求最短，最快，最少的问题（等权）都可以往广搜上面想想。。。理解每个”step“的含义，这里每一个step就是在正确的倒水路径上的每一次倒水，一共有6次倒水的方法，让每个“step”做这6个“动作”，然后一直这样往下”各个方向弥漫“，就一定会找到答案。
（注：对方向和步骤的理解不能太死板。要像理解面向对象一样。）

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

复制代码