python 解决母亲的奶牛问题

2744557306

题目描述】
- P0 K! d' t% A- j2 Y: n  I
+ s7 |6 C" W0 @        农夫约翰有三个容量分别为 A,B,C 升的挤奶桶。最开始桶 A 和桶 B 都是空的，而桶 C 里装满了牛奶。有时，约翰会将牛奶从一个桶倒到另一个桶中，直到被倒入牛奶的桶满了或者倒出牛奶的桶空了为止。这一过程中间不能有任何停顿，并且不会有任何牛奶的浪费。请你编写一个程序判断，当 A 桶是空的时候，C桶中可能包含多少升牛奶，找出所有的可能情况。
3 o) [2 e) U2 s6 z
【输入格式】
/ s- u1 n+ g, x. m
% U: @" d' ?6 O9 R, ?& V        共一行，包含三个整数 A,B,C。

【输出格式】
# q8 d/ z. H  g6 A
" R! f+ R+ b' H  q* K        共一行，包含若干个整数，表示 C 桶中牛奶存量的所有可能情况，请将这些数字按升序排列。

【数据范围】

        1≤A,B,C≤20
, T: P7 F0 Y/ Q( v) w2 g
【输入样例】
& d$ y6 V6 P0 k, O. c9 G+ e
8 9 10
【输出样例】

' R) s, I' |# M8 B2 J; P( l1 2 8 9 10
【解题思路】
8 n; ]1 Z- R2 M! h1 a7 e
        BFS简答模拟一下倒牛奶的过程。

1. from collections import *
   7 |: W  T1 M' m  H7 U( A
2. a,b,c = map(int,input().split())
   . ~\" ~2 I' j$ v
3. n = 22
   , m+ T& q5 W1 J
4. st = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]
   + F/ H& K/ R$ ]* m& }
5. 
   1 a  w( b* s5 |* y4 c
6. q = deque()\" y  R% B\" f  |/ y\" J! g1 I/ J
   
7. def ins(a_,b_,c_):
   # i. {& |) s6 }7 M0 b  W( ?
8.     global q
   \" P4 A2 M- I. f6 s% I) |
9.     if st[a_][b_][c_]:return, P* Q; m, a\" p
   
10.     q.append([a_,b_,c_])
    * K3 p9 @. O# o# Z$ z: o
11.     st[a_][b_][c_]=1- r+ G$ I% ?* @8 z0 Y9 _4 Q9 u
    
12. def bfs():
    ! n% t& U& i: v9 Q
13.     q.append([0,0,c])0 l1 n3 ]7 _: h( R) @7 c- a
    
14.     st[0][0][c]=1+ K- t$ ?4 z4 c1 r. S1 R\" ~1 t
    
15.     while q:# ?; M  C$ b% P+ P! c# Z
    
16.         a_,b_,c_ = q.popleft()
    : P: {+ o! O8 |9 I
17.         ins( a_-min(a_,b-b_) , b_+min(a_,b-b_) , c_ )' Y\" l3 @' S2 A/ V1 P+ _
    
18.         ins( a_-min(a_,c-c_) , b_ , c_+min(a_,c-c_) )+ P1 z% A- m1 H2 c: x7 b: N& G
    
19.         ins( a_+min(b_,a-a_) , b_-min(b_,a-a_) , c_ )
    - _\" L! o5 o. ~\" r- z
20.         ins( a_ , b_-min(b_,c-c_) , c_+min(b_,c-c_) ): g: X% v0 ?0 S\" ?
    
21.         ins( a_+min(c_,a-a_) , b_ , c_-min(c_,a-a_) )
    # W/ K. _6 \( ~\" q
22.         ins( a_ , b_+min(c_,b-b_) , c_-min(c_,b-b_) )
    7 k8 {0 @' p3 a) t
23. bfs()( l6 s/ j/ u& V2 \\" V( ^
    
24. for c_ in range(c+1):
    9 X, w  |; p) V3 @8 q1 J
25.     for b_ in range(b+1):
    & C  R8 }- N1 y. h# M; v
26.         if st[0][b_][c_]:) ?! ]6 x* _% f# t! M3 g: @0 P
    
27.             print(c_,end=' ')7 G5 i+ U( p; X0 l
    
28.             break

复制代码

3 ~* k2 e" ]7 @