USACO 1.4.2 Mother's Mil 母亲的牛奶(DFS)

2021年11月21日 阅读数:5
这篇文章主要向大家介绍USACO 1.4.2 Mother's Mil 母亲的牛奶(DFS),主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

Description

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

Input

单独的一行包括三个整数A,B和C。spa

Output

只有一行,列出当A桶是空的时候,C桶牛奶所剩量的全部可能性。code

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 }