python 解决母亲的奶牛问题

2744557306

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

【输入格式】
/ X/ b# n0 f- D% w2 z5 K
        共一行，包含三个整数 A,B,C。
. H2 Q, [" c0 ]
. e8 q5 c, I* ?【输出格式】

        共一行，包含若干个整数，表示 C 桶中牛奶存量的所有可能情况，请将这些数字按升序排列。

【数据范围】

, R$ Z- {+ U7 t; R8 J0 Z- L        1≤A,B,C≤20

【输入样例】

8 9 10
【输出样例】
  w1 [) W. N$ p% n
1 2 8 9 10
【解题思路】

        BFS简答模拟一下倒牛奶的过程。

1. from collections import *; \) q, y8 L2 k6 A
   
2. a,b,c = map(int,input().split())+ }8 P/ P3 _3 C\" o& O, h& {+ _
   
3. n = 22: Q+ G! f7 H7 q7 W8 o* W1 \
   
4. st = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]1 ~% h/ B8 B9 g& {7 U: J+ Y1 P- e
   
5. 4 J; ~/ D\" i4 L; H* q
   
6. q = deque()
   + b0 T/ w1 Q, D\" j, z
7. def ins(a_,b_,c_):\" z0 v- P' ~' b2 m5 R\" T
   
8.     global q7 t) t9 Q1 f/ K4 ?1 p0 D
   
9.     if st[a_][b_][c_]:return\" S) F$ M; R3 I
   
10.     q.append([a_,b_,c_])
    : T, t% S7 V3 d  p
11.     st[a_][b_][c_]=1
    # `: b' F\" _\" {/ ?\" q1 d
12. def bfs():  A0 r: D: j% U# _5 s$ H
    
13.     q.append([0,0,c]), v8 d0 U6 V  L* j% \3 O/ N8 }2 W' x5 Z
    
14.     st[0][0][c]=1
    1 a6 y( e2 \0 z
15.     while q:1 C+ p9 |& ?+ r# u9 {, o4 U
    
16.         a_,b_,c_ = q.popleft()
    * J3 ^( C0 \! B- r5 j- c2 L8 V
17.         ins( a_-min(a_,b-b_) , b_+min(a_,b-b_) , c_ )
    / i6 S- R6 e  _8 [
18.         ins( a_-min(a_,c-c_) , b_ , c_+min(a_,c-c_) )! F$ I9 M9 ]! B# R
    
19.         ins( a_+min(b_,a-a_) , b_-min(b_,a-a_) , c_ )
    + `7 ^' ?! [- g4 U* S
20.         ins( a_ , b_-min(b_,c-c_) , c_+min(b_,c-c_) ), Q, ~3 L: s7 v) I
    
21.         ins( a_+min(c_,a-a_) , b_ , c_-min(c_,a-a_) )
    $ O1 v6 z; g9 Z: R) Y  p# d
22.         ins( a_ , b_+min(c_,b-b_) , c_-min(c_,b-b_) )9 U/ ?# A, e! M0 b! F0 @( G
    
23. bfs()
    - Z* V1 M, i! P6 a' @- I# U, q
24. for c_ in range(c+1):9 u9 }2 Q2 e4 |( Z+ F3 l: W' H
    
25.     for b_ in range(b+1):
    \" [. l6 p. e) ~\" F- S
26.         if st[0][b_][c_]:
    ; E& ~3 l0 i& X6 I: _
27.             print(c_,end=' ')
    $ p\" a; ]8 M4 [  Z0 A6 ~7 s+ [& O
28.             break

复制代码

3 X( \' U& ?0 M