python 解决母亲的奶牛问题

2744557306

题目描述】

1 f. \) |& W1 l5 Q: ]' Z        农夫约翰有三个容量分别为 A,B,C 升的挤奶桶。最开始桶 A 和桶 B 都是空的，而桶 C 里装满了牛奶。有时，约翰会将牛奶从一个桶倒到另一个桶中，直到被倒入牛奶的桶满了或者倒出牛奶的桶空了为止。这一过程中间不能有任何停顿，并且不会有任何牛奶的浪费。请你编写一个程序判断，当 A 桶是空的时候，C桶中可能包含多少升牛奶，找出所有的可能情况。
$ x) l7 E  {5 z) `9 W- u4 E  j2 ~8 z
【输入格式】

) v' c. g# _& E$ k2 m( S% E7 |        共一行，包含三个整数 A,B,C。
6 o' X0 o% Q6 Y" q4 h* z: R
  j5 b0 l5 C; F# M【输出格式】

( W: h4 T8 g& {+ G        共一行，包含若干个整数，表示 C 桶中牛奶存量的所有可能情况，请将这些数字按升序排列。
( d9 g" \4 x. G0 j7 n; j
【数据范围】
, _: c& ]. @" t- S5 [% C  @
        1≤A,B,C≤20

【输入样例】

4 ?9 E" l' Q9 |" h7 r8 9 10
【输出样例】

" v8 d. h0 j+ e8 Q  K1 2 8 9 10
; p! ^, s2 y* ~ 【解题思路】
8 n+ t  M) d; t9 }* D
        BFS简答模拟一下倒牛奶的过程。

1. from collections import *# F- L2 ~3 b7 h. ^) H
   
2. a,b,c = map(int,input().split())) q/ z& b: `' N: D* R) b
   
3. n = 224 p2 b# x4 }7 p- S
   
4. st = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]# l# o- }6 h6 p( k8 u' Z  ?
   
5. 
   , M0 h/ ^9 f: ~6 v
6. q = deque()
     x  \4 G2 n% p: L5 z2 f. Z
7. def ins(a_,b_,c_):/ R: K% t) Z8 |& A7 y
   
8.     global q+ M4 C5 ]$ N. {6 Z/ S: I$ e
   
9.     if st[a_][b_][c_]:return
   8 g* n, `% c, O0 P; `9 P  }' K& y
10.     q.append([a_,b_,c_])
    - g9 _6 c7 J, N1 [' n! X- a
11.     st[a_][b_][c_]=1# q# u: Y' H4 v- n- [: H
    
12. def bfs():; ^- v. v/ G6 K4 D6 i* G
    
13.     q.append([0,0,c])
    ( V: B5 G6 O9 q) f
14.     st[0][0][c]=1
    ' _& i\" u; v, l9 v, t5 v. j, c
15.     while q:3 m+ E6 R, _( M, c) [\" W6 F
    
16.         a_,b_,c_ = q.popleft()+ M( U' _# }7 ~7 S' G. y/ U
    
17.         ins( a_-min(a_,b-b_) , b_+min(a_,b-b_) , c_ )
    ) E, ~2 f9 Q8 U7 B
18.         ins( a_-min(a_,c-c_) , b_ , c_+min(a_,c-c_) )
    , D' D0 U% k1 i9 s! T& ?8 ~% T
19.         ins( a_+min(b_,a-a_) , b_-min(b_,a-a_) , c_ )\" c# W- S, }8 d1 x
    
20.         ins( a_ , b_-min(b_,c-c_) , c_+min(b_,c-c_) )8 ]; Q1 K8 @2 O- W- I5 I
    
21.         ins( a_+min(c_,a-a_) , b_ , c_-min(c_,a-a_) )
    * t. ~9 @& S) \. y
22.         ins( a_ , b_+min(c_,b-b_) , c_-min(c_,b-b_) )' o8 p/ B# Z1 H2 ^8 G8 Z
    
23. bfs()
    ' p& h6 m* y' V0 U\" M. C; x# \  ^, D3 u
24. for c_ in range(c+1):
    . e7 ?! G  o: @  g9 v! L! s
25.     for b_ in range(b+1):
    ! `. n4 L6 z% g5 {: A4 c5 a
26.         if st[0][b_][c_]:
    9 G. G, }4 Z1 f9 p
27.             print(c_,end=' ')
    2 H) a$ g# C9 k) v# V. N1 S, W5 d+ a
28.             break

复制代码

& _9 }% l( p; j