python 解决母亲的奶牛问题

2744557306

题目描述】

        农夫约翰有三个容量分别为 A,B,C 升的挤奶桶。最开始桶 A 和桶 B 都是空的，而桶 C 里装满了牛奶。有时，约翰会将牛奶从一个桶倒到另一个桶中，直到被倒入牛奶的桶满了或者倒出牛奶的桶空了为止。这一过程中间不能有任何停顿，并且不会有任何牛奶的浪费。请你编写一个程序判断，当 A 桶是空的时候，C桶中可能包含多少升牛奶，找出所有的可能情况。

; K0 V1 o2 Y* M- K8 G) G【输入格式】

        共一行，包含三个整数 A,B,C。

3 A: k. t$ q2 w* H【输出格式】
: M! q/ S) B" c9 k* _% M+ F' S
        共一行，包含若干个整数，表示 C 桶中牛奶存量的所有可能情况，请将这些数字按升序排列。
0 g5 K" [$ y  e+ ?- W% y
【数据范围】

        1≤A,B,C≤20

【输入样例】
0 _, \; q5 ]. c# M3 v2 L
8 9 10
& k4 O2 e' n1 K9 [; j2 m【输出样例】

1 2 8 9 10
【解题思路】
4 |$ B! M( S6 \
        BFS简答模拟一下倒牛奶的过程。

1. from collections import *% ]8 K$ B7 x5 w5 [$ w' Y
   
2. a,b,c = map(int,input().split())
   ) k9 W+ D& P( `1 }6 |1 i( ~
3. n = 22( E& O3 x; ~. e( `% o% n% |
   
4. st = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]
   ) D- A1 g) O5 v6 j8 u
5. 7 V. e% P( {- Q+ T/ L$ b
   
6. q = deque()
   + {  f) ?; ]! g# e& X
7. def ins(a_,b_,c_):1 R\" p/ D  C$ P% f. Y
   
8.     global q8 S7 _\" Q' [6 Y9 y2 N$ \: ^9 P# l- w
   
9.     if st[a_][b_][c_]:return
   ! q0 ?, \* `# C\" s1 H: x
10.     q.append([a_,b_,c_])
    ! B6 ~6 {8 z* E3 @/ S; T
11.     st[a_][b_][c_]=1
    ) ]* e; C! L$ n2 ?
12. def bfs():
    - v  H+ i5 C! x) f
13.     q.append([0,0,c])
    9 p- J) s4 ]: E: A! t8 c' W+ k
14.     st[0][0][c]=1  m5 O5 w6 I! m
    
15.     while q:
      x4 `, `- a5 J$ X, x
16.         a_,b_,c_ = q.popleft(), }5 n- a, Y6 l( _9 `\" K5 E- L% @\" R
    
17.         ins( a_-min(a_,b-b_) , b_+min(a_,b-b_) , c_ )# ?: |5 C# o  j7 }0 x( v% ~
    
18.         ins( a_-min(a_,c-c_) , b_ , c_+min(a_,c-c_) )
    ( |4 f/ v7 z7 E
19.         ins( a_+min(b_,a-a_) , b_-min(b_,a-a_) , c_ )
    + o2 T( e2 k  u1 i# G# [
20.         ins( a_ , b_-min(b_,c-c_) , c_+min(b_,c-c_) )+ {% E& N/ d2 L4 G
    
21.         ins( a_+min(c_,a-a_) , b_ , c_-min(c_,a-a_) )1 ^0 _* G; u+ J0 ^* z
    
22.         ins( a_ , b_+min(c_,b-b_) , c_-min(c_,b-b_) )2 M+ X6 [* }( P, I7 |1 a+ V- b% s3 A
    
23. bfs()
    . K4 k& B' K8 j5 t3 j4 j+ W: F
24. for c_ in range(c+1):3 d) \1 C: b- G4 F
    
25.     for b_ in range(b+1):6 e9 Z1 j; M; }1 _3 r
    
26.         if st[0][b_][c_]:
    $ Y3 j, n3 ~5 J+ [4 _
27.             print(c_,end=' ')
    ) ^\" I* a: b1 W/ M
28.             break

复制代码