python 解决母亲的奶牛问题

2744557306

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

6 J! \1 t; u# T- [: V7 I【输入格式】
% f" h! {  C8 r2 A& m
        共一行，包含三个整数 A,B,C。
2 C4 g+ q* s$ a, Y. a9 j( b# s* s! h
【输出格式】

! I4 A2 X) n" s8 p3 F0 T' r        共一行，包含若干个整数，表示 C 桶中牛奶存量的所有可能情况，请将这些数字按升序排列。
& T4 e2 e4 }& ]
【数据范围】
7 B% v4 T1 z9 {+ ]# s$ o
        1≤A,B,C≤20
0 x2 X, g4 J2 Y, h$ K( V1 c
( Q& C3 O. M% f, G8 {% q【输入样例】

8 9 10
【输出样例】
( X# K& {* R' y$ |
+ _5 ]6 A% \/ Y5 [% n1 2 8 9 10
5 K+ c3 }0 v9 y, r 【解题思路】
1 ?# X) h1 C' N8 m; s* l
        BFS简答模拟一下倒牛奶的过程。

1. from collections import *
   8 L) |$ a2 G  K3 h3 c
2. a,b,c = map(int,input().split())
   \" i0 Q; @3 R) O0 P, T2 I6 U
3. n = 22
   ! t, ^4 a2 A5 \
4. st = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]+ L% D2 o8 j& ~3 r# U% R
   
5. 
   ; W* P* s\" r. n( Z\" W; |0 d% a
6. q = deque()' I$ z% Y1 {9 p7 F6 V
   
7. def ins(a_,b_,c_):8 B# h7 v6 q& x6 W; d4 x! |
   
8.     global q
   $ X' R( f' \% Y
9.     if st[a_][b_][c_]:return
   / {\" D$ U+ k5 }, C% U1 Z
10.     q.append([a_,b_,c_])
    * V: x- f2 M; q0 G/ C( g
11.     st[a_][b_][c_]=1% Q$ b+ S+ q% M$ A; h& i3 |- I
    
12. def bfs():
    9 F9 p6 E1 f! A\" o
13.     q.append([0,0,c])  j7 m\" z, n\" k9 t7 m6 z
    
14.     st[0][0][c]=1% D* s0 S, _: }
    
15.     while q:8 h4 D+ ^9 _3 ^! J6 r8 K! W\" u
    
16.         a_,b_,c_ = q.popleft()+ V5 N& M, p5 Q1 g8 u7 U/ P
    
17.         ins( a_-min(a_,b-b_) , b_+min(a_,b-b_) , c_ )
    * |* {& J\" O. y- k2 L: l* e+ [5 z
18.         ins( a_-min(a_,c-c_) , b_ , c_+min(a_,c-c_) )+ f7 ]* \' m2 g7 [) F1 A% ?
    
19.         ins( a_+min(b_,a-a_) , b_-min(b_,a-a_) , c_ )+ y: L4 \5 C\" b2 u
    
20.         ins( a_ , b_-min(b_,c-c_) , c_+min(b_,c-c_) )
    * `1 m# B0 C7 x3 f: I% M
21.         ins( a_+min(c_,a-a_) , b_ , c_-min(c_,a-a_) ); F. N, I5 y+ Z! Z8 ^
    
22.         ins( a_ , b_+min(c_,b-b_) , c_-min(c_,b-b_) )2 D( x7 i0 V; O. F# s( \
    
23. bfs()6 n( L8 y+ @  U3 L
    
24. for c_ in range(c+1):
    % ]/ j( I& H2 ~# a
25.     for b_ in range(b+1):
    $ Q) S5 u! G0 @\" n: ]
26.         if st[0][b_][c_]:
    $ h6 A4 H& z, D7 W% }4 q
27.             print(c_,end=' ')
    5 H$ p: s+ c\" R. v3 p* t1 M6 n' J1 ~
28.             break

复制代码

& a9 F& F7 d/ W! H, j7 ^, s