python 解决母亲的奶牛问题

2744557306

题目描述】
. y" i6 R$ q- j
; R6 D5 E- d! Q, H& U% X        农夫约翰有三个容量分别为 A,B,C 升的挤奶桶。最开始桶 A 和桶 B 都是空的，而桶 C 里装满了牛奶。有时，约翰会将牛奶从一个桶倒到另一个桶中，直到被倒入牛奶的桶满了或者倒出牛奶的桶空了为止。这一过程中间不能有任何停顿，并且不会有任何牛奶的浪费。请你编写一个程序判断，当 A 桶是空的时候，C桶中可能包含多少升牛奶，找出所有的可能情况。
# R3 @, [* M0 {' q' q  g
【输入格式】

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

# X& z% w. q/ [3 D: _【输出格式】
1 P: D4 x! G: K/ i% N
) J# z# x8 u% [0 n        共一行，包含若干个整数，表示 C 桶中牛奶存量的所有可能情况，请将这些数字按升序排列。
. h6 r/ H! P- i* j3 p: K4 j. H( I
【数据范围】

! z, t( [* n8 H' W6 E        1≤A,B,C≤20

【输入样例】
$ [8 O' I# X* ?7 d) z8 c
6 _! E4 ?' i! v: U8 9 10
$ D. v( e* [* B4 `7 }4 H【输出样例】
2 |) e* p# }1 P! T9 l
1 2 8 9 10
. `( }3 Y/ P4 s8 ^7 Y" n 【解题思路】
  J# B3 M3 Y* ~, W  t( r6 o/ q% b: `
& [; J- B8 F( R0 c6 s3 S        BFS简答模拟一下倒牛奶的过程。

1. from collections import *, h  |. t+ q4 m4 J% A
   
2. a,b,c = map(int,input().split())
   # v! `, E6 Z* k- O% x: B
3. n = 222 @, d$ C- G, ^
   
4. st = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]
   9 L; n9 r5 V8 f+ m& u! ~! R/ \) C1 @
5. : W  b! G& |: l4 U, u\" s& H
   
6. q = deque()
   ) x! ?! ^/ F- p3 \+ K( L. A: @
7. def ins(a_,b_,c_):
   $ T' z& Z; Y4 T1 d& q8 H4 {) h, E# j
8.     global q
   4 H8 i! d; Q- @% q\" Z7 P
9.     if st[a_][b_][c_]:return
   : }3 P\" i: ~. w, p\" L$ j& v0 ~6 \) s
10.     q.append([a_,b_,c_])+ r* [! o: S( D, y( G6 W
    
11.     st[a_][b_][c_]=1' @  K! j. E& o* d1 B
    
12. def bfs():% b' G5 j& b% z3 a  E5 Y
    
13.     q.append([0,0,c])
    ' L' ?  F( m5 V- N* B
14.     st[0][0][c]=1
    \" H% D( j8 y' n7 s& F  Z) M5 j$ y
15.     while q:
    ' \  l! Y- |! W! q1 D
16.         a_,b_,c_ = q.popleft(); ?- g# j) Z( L\" p
    
17.         ins( a_-min(a_,b-b_) , b_+min(a_,b-b_) , c_ )
    9 x* m1 n7 |, G3 M
18.         ins( a_-min(a_,c-c_) , b_ , c_+min(a_,c-c_) )
    / `( `' B/ i0 l$ X  v, M
19.         ins( a_+min(b_,a-a_) , b_-min(b_,a-a_) , c_ )3 e' `\" J) S. F2 ]
    
20.         ins( a_ , b_-min(b_,c-c_) , c_+min(b_,c-c_) )
    : n5 t% Q% G$ w# K
21.         ins( a_+min(c_,a-a_) , b_ , c_-min(c_,a-a_) )
    2 a# G! C: g# t\" Z4 c) A( S
22.         ins( a_ , b_+min(c_,b-b_) , c_-min(c_,b-b_) )
    2 m, k0 o3 X$ R. y) T  `, O
23. bfs()9 V: R) i# E% x
    
24. for c_ in range(c+1):
    2 v$ e5 L4 f( C0 i7 n  c# H
25.     for b_ in range(b+1):  X& }4 M* ]6 E/ a; P2 r1 @
    
26.         if st[0][b_][c_]:) v# d$ U% g  K3 G/ F% e
    
27.             print(c_,end=' ')
    ( B) u) h, v' ^) B' p
28.             break

复制代码