Description
农民约翰有三个容量分别是A,B,C升的桶,A,B,C分别是三个从1到20的整数,最初,A和B桶都是空的,而C桶是装满牛奶的。有时,约翰把牛奶从一个桶倒到另一个桶中,直到被灌桶装满或原桶空了。当然每一次灌注都是完全的。由于节约,牛奶不会有丢失。 写一个程序去帮助约翰找出当A桶是空的时候,C桶中牛奶所剩量的所有可能性。
Input
单独的一行包括三个整数A,B和C。
Output
只有一行,列出当A桶是空的时候,C桶牛奶所剩量的所有可能性。
Sample Input
8 9 10
Sample Output
1 2 8 9 10
解题思路:真是尴尬啊,当时做完这道题直接就将代码赋值过来了,并没有直接写题解,还是在同学的提醒下。。。。汗颜啊。我当时第一感觉是想分情况来
讨论,但是忘记了我们不知道他倒了几次,所有不能来分情况讨论(可怜了我9个if)。那该怎么办呢?归根到底倒牛奶也就是a->b,a->c,b->a,b->c,c->a,
c->b这六种情况嘛,但我们还要根据题意能不能倒满会不会有剩余,每一种倒法再分成两种情况。
但是每次倒完后的状态不一定一样的,不一样的状态在进行六种不同方式的倾倒,又可以产生不一样的状态。这就需要来记录每个状态是否出现过,当出现过时就直接返回到函数出口,
进行上一层的下一次变换,若没有出现过此状态就继续进行这六种方式的变换。深度优先搜索示意图如下:那么就选择使用DFS枚举这些情况就可以了。
1 #include<cstring>
2 #include<cstdio>
3 #include<algorithm>
4 #define MAX 21
5 using namespace std;
6 int A,B,C;
7 int vis[MAX][MAX][MAX];///记录状态是否访问过
8 int r[MAX];
9 void DFS(int a,int b,int c)
10 {
11 if(vis[a][b][c]==1)///当这种状态出现过就直接返回函数出口,进行下一层变换
12 {
13 return ;
14 }
15 else
16 {
17 vis[a][b][c]=1;
18 }
19 if(a==0&&!r[c])///记录a为0时,c的值
20 {
21 r[c]=1;
22 }
23 if(c>=A-a)///c->a
24 {
25 DFS(A,b,c-A+a);
26 }
27 else
28 {
29 DFS(a+c,b,0);
30 }
31 if(c>=B-b)///c->b
32 {
33 DFS(a,B,c-B+b);
34 }
35 else
36 {
37 DFS(a,b+c,0);
38 }
39 if(b>=A-a)///b->a
40 {
41 DFS(A,b-A+a,c);
42 }
43 else
44 {
45 DFS(a+b,0,c);
46 }
47 if(b>=C-c)///b->c
48 {
49 DFS(a,b-C+c,C);
50 }
51 else
52 {
53 DFS(a,0,c+b);
54 }
55 if(a>=B-b)///a->b
56 {
57 DFS(a-B+b,B,c);
58 }
59 else
60 {
61 DFS(0,b+a,c);
62 }
63 if(a>=C-c)///a-c
64 {
65 DFS(a-C+c,b,C);
66 }
67 else
68 {
69 DFS(0,b,c+a);
70 }
71 }
72 int main()
73 {
74 int i,counts;
75 scanf("%d%d%d",&A,&B,&C);
76 DFS(0,0,C);
77 counts=0;
78 for(i=0;i<=C;i++)
79 {
80 if(r[i])
81 {
82 counts++;
83 if(counts==1)
84 {
85 printf("%d",i);
86 }
87 else
88 {
89 printf(" %d",i);
90 }
91 }
92 }
93 printf("\n");
94 return 0;
95 }