python 解决母亲的奶牛问题

2744557306

题目描述】

        农夫约翰有三个容量分别为 A,B,C 升的挤奶桶。最开始桶 A 和桶 B 都是空的，而桶 C 里装满了牛奶。有时，约翰会将牛奶从一个桶倒到另一个桶中，直到被倒入牛奶的桶满了或者倒出牛奶的桶空了为止。这一过程中间不能有任何停顿，并且不会有任何牛奶的浪费。请你编写一个程序判断，当 A 桶是空的时候，C桶中可能包含多少升牛奶，找出所有的可能情况。
2 C  l) w( x( E, J$ _8 {
【输入格式】

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

【输出格式】
* t3 p/ \  [$ P: _' Y" R
        共一行，包含若干个整数，表示 C 桶中牛奶存量的所有可能情况，请将这些数字按升序排列。
% h3 P; S0 G) ?2 a
% ?% k, s9 Q. h, g【数据范围】

% |$ I+ P# g( L+ p5 Z$ w2 p        1≤A,B,C≤20
- [9 t( b2 {1 [/ c+ b, n3 r
6 K0 f) [% K9 p; W  i* s【输入样例】

6 V* ^/ k, G3 G* d) O! b8 9 10
# E+ D8 t, O* @, C$ F: Q* J【输出样例】

+ T4 d) |; R' Y- c1 o; c1 2 8 9 10
! L, {5 c  l4 A- C& r 【解题思路】

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

1. from collections import *
   8 @6 o- N+ e; e+ {3 n( b0 D5 T0 q% X
2. a,b,c = map(int,input().split())
   4 p- j' K5 y2 U% ~4 N
3. n = 22
   ' |5 p- b0 i. M4 y
4. st = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]- \6 r7 ?7 E5 I* i% F\" }1 P- J
   
5. 
   5 M+ k* Z3 v& @! e$ c1 K
6. q = deque()
   0 U# O1 D' x\" m7 @\" A0 u
7. def ins(a_,b_,c_):- |6 ~! p, k) u
   
8.     global q; {& D7 ~& H8 a
   
9.     if st[a_][b_][c_]:return
   9 W! x8 B1 U& l- c, `7 ^
10.     q.append([a_,b_,c_])- V: S+ q8 X! T; Z' s3 S- n- U) V& u. R
    
11.     st[a_][b_][c_]=1
    : e) z( {, ]) o. \# ^- _* d$ Q
12. def bfs():. S4 G! N: a! j  T6 v' y0 A+ _0 S
    
13.     q.append([0,0,c])
    , R/ W7 y5 w$ m4 L) d. O. m
14.     st[0][0][c]=1
    ; B2 v1 r0 i6 e  b
15.     while q:
    * J3 M9 w8 |3 U  z1 m4 F5 X
16.         a_,b_,c_ = q.popleft()
    0 [1 c. }2 N: t4 j2 t4 B/ Q
17.         ins( a_-min(a_,b-b_) , b_+min(a_,b-b_) , c_ )  r0 |1 |' I1 v% n1 L0 J9 e
    
18.         ins( a_-min(a_,c-c_) , b_ , c_+min(a_,c-c_) )
    % }7 k6 n7 \4 c' m
19.         ins( a_+min(b_,a-a_) , b_-min(b_,a-a_) , c_ )
    1 m/ y7 ~\" D. D' L
20.         ins( a_ , b_-min(b_,c-c_) , c_+min(b_,c-c_) )7 Z( G1 y# Q( [1 P' x
    
21.         ins( a_+min(c_,a-a_) , b_ , c_-min(c_,a-a_) )1 V+ t) N4 h, a
    
22.         ins( a_ , b_+min(c_,b-b_) , c_-min(c_,b-b_) )8 e3 q3 y3 X! H/ y+ F  ~) H3 z6 r, N
    
23. bfs()1 ?  B' W* T2 u6 ^
    
24. for c_ in range(c+1):, r, V, E0 V4 K. P4 F
    
25.     for b_ in range(b+1):
      R. E6 d5 I7 s+ S$ x
26.         if st[0][b_][c_]:' J; K9 V2 l8 ?# a& g
    
27.             print(c_,end=' ')& l$ M0 r$ l: V# Q\" i6 x7 `* o
    
28.             break

复制代码