python 解决母亲的奶牛问题

2744557306

题目描述】
- A8 ^, H: s1 Y; U% f
1 e% P3 ^% Q  I; L) h6 _        农夫约翰有三个容量分别为 A,B,C 升的挤奶桶。最开始桶 A 和桶 B 都是空的，而桶 C 里装满了牛奶。有时，约翰会将牛奶从一个桶倒到另一个桶中，直到被倒入牛奶的桶满了或者倒出牛奶的桶空了为止。这一过程中间不能有任何停顿，并且不会有任何牛奶的浪费。请你编写一个程序判断，当 A 桶是空的时候，C桶中可能包含多少升牛奶，找出所有的可能情况。

( z. G. E' P/ c5 G9 p( N/ ^. ^' c4 y+ W8 o【输入格式】
' h& V. r2 U* }' w
        共一行，包含三个整数 A,B,C。
/ ?* ?8 V  e) \: ^: h9 V0 W* V
9 v$ J3 S% \5 d( g: [" z) B: E【输出格式】
) Y  H; o5 D3 ~% N8 @
" y+ N9 z. v$ ^# f! K" l        共一行，包含若干个整数，表示 C 桶中牛奶存量的所有可能情况，请将这些数字按升序排列。

" W+ U+ r" ^# u0 }% ]4 z4 T9 G: }0 |【数据范围】
! A0 Y1 h0 u! x& z* c
        1≤A,B,C≤20
3 T! s( K& w3 G1 J, W
【输入样例】
5 o! S% V9 w9 J5 n
8 9 10
【输出样例】
* s8 A4 k! E1 T& p* b5 m! X
9 H- }# \  Z3 F& ?1 2 8 9 10
【解题思路】
4 t8 W$ _6 Y8 ^8 v, ~
0 A  _5 Y+ t9 q* h        BFS简答模拟一下倒牛奶的过程。

1. from collections import *8 A5 o8 t% m\" w4 w. }+ N# o* ^7 k, L
   
2. a,b,c = map(int,input().split())7 E0 h5 ^4 A! T5 z9 Y
   
3. n = 22% c1 \$ w1 l# k
   
4. st = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]% P9 l# O/ V) K5 K2 p1 t
   
5. 
   7 D  Y4 |% z/ Y! `2 S7 ^
6. q = deque()- V+ ~( x2 P# B) @8 _\" t
   
7. def ins(a_,b_,c_):* h8 G1 o# C0 A: I  r7 }
   
8.     global q0 Q3 d# ^7 F% u' b6 S; a5 Z
   
9.     if st[a_][b_][c_]:return
   / @5 d0 B3 L7 g% t0 V
10.     q.append([a_,b_,c_])
    & L, J( Q: V- ~\" O
11.     st[a_][b_][c_]=1
    8 @# c3 v* K, S' f' a3 g
12. def bfs():2 Q  d) J- W. n: r* L2 O
    
13.     q.append([0,0,c])
    . P5 S8 b: v' x! ?/ U  J# v
14.     st[0][0][c]=1
    4 T0 D% D5 S% r3 o# J. A0 \; l/ J
15.     while q:
    ' Z3 `! B( @* u6 U0 }
16.         a_,b_,c_ = q.popleft(); A, h6 z\" ]1 q8 N! d
    
17.         ins( a_-min(a_,b-b_) , b_+min(a_,b-b_) , c_ )
    . n. w* b. e# {% o& o
18.         ins( a_-min(a_,c-c_) , b_ , c_+min(a_,c-c_) )
    ) N% a7 [8 H1 R2 O
19.         ins( a_+min(b_,a-a_) , b_-min(b_,a-a_) , c_ )
    \" s: J; @; z! u* w! E/ e8 ]2 E
20.         ins( a_ , b_-min(b_,c-c_) , c_+min(b_,c-c_) )
      ^6 W2 J/ k6 R, n
21.         ins( a_+min(c_,a-a_) , b_ , c_-min(c_,a-a_) )
    1 ~; F7 h% u: S. w7 X. ^
22.         ins( a_ , b_+min(c_,b-b_) , c_-min(c_,b-b_) )
    - R3 {: g6 B( ?% I( p$ L
23. bfs()
    ; V5 E$ b6 `* o
24. for c_ in range(c+1):
    5 C\" I. h. y4 M  C! K4 x
25.     for b_ in range(b+1):9 |- Y$ I6 ^9 @/ |
    
26.         if st[0][b_][c_]:
    5 M7 x# M9 E, \  u; p: c
27.             print(c_,end=' ')
      m! u' H; }  {+ h3 z0 P: c
28.             break

复制代码