python 解决母亲的奶牛问题

2744557306

题目描述】
. O( Z# e/ w7 Z9 r" u
        农夫约翰有三个容量分别为 A,B,C 升的挤奶桶。最开始桶 A 和桶 B 都是空的，而桶 C 里装满了牛奶。有时，约翰会将牛奶从一个桶倒到另一个桶中，直到被倒入牛奶的桶满了或者倒出牛奶的桶空了为止。这一过程中间不能有任何停顿，并且不会有任何牛奶的浪费。请你编写一个程序判断，当 A 桶是空的时候，C桶中可能包含多少升牛奶，找出所有的可能情况。

【输入格式】

# f7 L* U0 n; E" b        共一行，包含三个整数 A,B,C。

【输出格式】

        共一行，包含若干个整数，表示 C 桶中牛奶存量的所有可能情况，请将这些数字按升序排列。
0 j- M5 f4 K3 k0 l- b- g7 W
【数据范围】
5 g1 w6 h$ {1 l, [7 j& J
) }. b' Y1 }% p% p& [        1≤A,B,C≤20
- i5 x' p+ H% s/ K
【输入样例】
. n% q( D$ O2 s% ^$ e/ f, \
% N% |, q- T/ w3 h& b, Q3 J/ u8 9 10
2 V! C$ T6 X& B0 k5 x! j4 u; K【输出样例】
$ ^0 j3 Q( M* `& O$ t4 k# A6 e
' J: p6 ]" \) J5 ^' z$ G1 2 8 9 10
【解题思路】
( t9 }! p8 ~# M. ^$ J
$ u' g# d- p0 B! O; r        BFS简答模拟一下倒牛奶的过程。

1. from collections import *
   $ m1 k0 l- f& |
2. a,b,c = map(int,input().split())+ ]2 F! I% O6 q7 z& q1 I2 H2 O
   
3. n = 22+ @9 }( F$ r8 ?% v8 a4 L8 K  @
   
4. st = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]
   ! d/ r- L\" Q; d- J$ e* r  }( j
5. 
   4 ^+ [' |$ l# J1 R
6. q = deque()
   9 p- H0 E' J/ E6 c
7. def ins(a_,b_,c_):
   , T' k4 d- _5 F7 `5 C
8.     global q
   + G* b' B0 y7 D  I0 B* ]
9.     if st[a_][b_][c_]:return7 R8 l\" p' r* ^. U! @
   
10.     q.append([a_,b_,c_])
    ; v9 V) ]5 w6 Y9 j2 J( p
11.     st[a_][b_][c_]=1  B0 O8 B+ k( N) q5 n8 |
    
12. def bfs():
    - P6 k  h; n4 X- p& \5 O2 ?
13.     q.append([0,0,c])
    , |. B5 w# {/ ?9 x% |' E' g
14.     st[0][0][c]=1
    ( }' M/ X+ ?+ N\" I2 R8 p2 e
15.     while q:
    - j# F( B1 [+ Z
16.         a_,b_,c_ = q.popleft()) H' E* U, k- |! p
    
17.         ins( a_-min(a_,b-b_) , b_+min(a_,b-b_) , c_ )8 Q/ ]0 V  Q, u+ H; C* U4 Z4 U- }
    
18.         ins( a_-min(a_,c-c_) , b_ , c_+min(a_,c-c_) )
    ! M( K/ v8 |! n0 r. B7 Q6 @6 Y. [
19.         ins( a_+min(b_,a-a_) , b_-min(b_,a-a_) , c_ )
    8 x+ ^) d* Z* L: i% h8 c
20.         ins( a_ , b_-min(b_,c-c_) , c_+min(b_,c-c_) )- [1 b2 ^. p5 x
    
21.         ins( a_+min(c_,a-a_) , b_ , c_-min(c_,a-a_) )
    2 u* k7 X- ]  }, r( z) p1 P
22.         ins( a_ , b_+min(c_,b-b_) , c_-min(c_,b-b_) ): m' U5 E4 `: O2 h! U
    
23. bfs()6 ?  g  G: [4 l; s
    
24. for c_ in range(c+1):5 ?1 p$ [9 \7 [& C+ i
    
25.     for b_ in range(b+1):
    * v; X\" @' D6 }% L* a. V
26.         if st[0][b_][c_]:; P9 O- O' k3 @  _
    
27.             print(c_,end=' ')
    3 |% ]7 m3 l  ]% r# x
28.             break

复制代码