UPC-1526 母亲的牛奶【搜索】

题目描述

农民约翰有三个容量分别是A、B、C升的桶，A、B、C分别是三个从1到20的整数，最初，A和B桶都是空的，而C桶是装满牛奶的。有时，约翰把牛奶从一个桶倒到另一个桶中，直到被灌桶装满或原桶空了。当然每一次灌注都是完全的，由于节约，牛奶不会丢失。写一个程序去帮助约翰找出当A桶是空的时候，C桶中牛奶所剩量的所有可能性。

输入

单独的1行，包括三个整数A，B和C。

输出

只有1行，列出当A桶是空的时候，C桶牛奶所剩量的所有可能性。

样例输入

8 9 10

样例输出

1 2 8 9 10

可能的倒法为
A-->B　　A-->C
B-->A　　B-->C
C-->A　　C-->B
在这六种倒法中，又分别包含了两种情况：被灌桶装满或原桶空了。
所以，我们用dfs(a,b,c)进行深搜。用三维数组vis[a][b][c]标志在三个桶中的牛奶分别为a,b,c时的情况。用一维数组num[c]来记录A中的牛奶为0时，C中的牛奶为c。
每次深搜返回的条件为vis[a][b][c]==1，接下来便是对每种情况的列举。

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 bool vis[25][25][25],num[25];
 5 int va,vb,vc;
 6 void dfs(int a,int b,int c)
 7 {
 8     if(vis[a][b][c])    return ;
 9     else    vis[a][b][c]=1;
10     if(a==0)    num[c]=1;
11     int p;
12     if(a!=0&&vb>b)
13     {
14         p=min(vb-b,a);
15         dfs(a-p,b+p,c);
16     }
17     if(a!=0&&vc>c)
18     {
19         p=min(vc-c,a);
20         dfs(a-p,b,c+p);
21     }
22     if(b!=0&&va>a)
23     {
24         p=min(va-a,b);
25         dfs(a+p,b-p,c);
26     }
27     if(b!=0&&vc>c)
28     {
29         p=min(vc-c,b);
30         dfs(a,b-p,c+p);
31     }
32     if(c!=0&&va>a)
33     {
34         p=min(va-a,c);
35         dfs(a+p,b,c-p);
36     }
37     if(c!=0&&vb>b)
38     {
39         p=min(vb-b,c);
40         dfs(a,b+p,c-p);
41     }
42 }
43 int main()
44 {
45     cin>>va>>vb>>vc;
46     dfs(0,0,vc);
47     int temp=20;
48     while(!num[temp])
49     {
50         temp--;
51     }
52     for(int i=0;i<temp;i++)
53     {
54         if(num[i])  cout<<i<<" ";
55     }
56     cout<<temp<<endl;
57 }

View Code

如有错误，请指正，感谢！