python 解决母亲的奶牛问题

2744557306

题目描述】

  U; r/ x- x7 h; A4 G- ^        农夫约翰有三个容量分别为 A,B,C 升的挤奶桶。最开始桶 A 和桶 B 都是空的，而桶 C 里装满了牛奶。有时，约翰会将牛奶从一个桶倒到另一个桶中，直到被倒入牛奶的桶满了或者倒出牛奶的桶空了为止。这一过程中间不能有任何停顿，并且不会有任何牛奶的浪费。请你编写一个程序判断，当 A 桶是空的时候，C桶中可能包含多少升牛奶，找出所有的可能情况。
; l2 R7 y& s0 _/ o; J& o* b  y  E
【输入格式】

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

' z1 B$ B2 [1 E5 U【输出格式】

        共一行，包含若干个整数，表示 C 桶中牛奶存量的所有可能情况，请将这些数字按升序排列。
+ L& Q( e9 f: w
【数据范围】

" }2 `" w; b: j4 y        1≤A,B,C≤20

# G0 ^, N9 P( ?. r9 `6 g【输入样例】
. G' p( z6 K, D
( g8 k8 E7 U* s" u8 9 10
* x: D9 u0 B. i/ U" n【输出样例】

8 \4 `5 o( Q2 s9 F. ?7 S. j$ ^- U/ D* a3 b1 2 8 9 10
) ~# j6 x. |4 W# }2 _) c$ ]8 t 【解题思路】
1 C( W' E5 e% J) W' R. z
        BFS简答模拟一下倒牛奶的过程。

1. from collections import *
   2 _7 ]' [% ?6 {
2. a,b,c = map(int,input().split())4 D7 X. t7 S3 a+ {8 r1 @! {1 Q
   
3. n = 220 L7 f( j8 W8 R7 @9 Q# J. H
   
4. st = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]
   3 _( @5 ]; Q& w; F
5. & n$ s/ c! L9 r  H
   
6. q = deque()
   3 G6 S4 s# O: Q8 H
7. def ins(a_,b_,c_):
     Q) Y; a4 f# M! J0 I
8.     global q3 Y8 U2 {/ f; U9 o% V
   
9.     if st[a_][b_][c_]:return
   1 q% e\" D: }( m
10.     q.append([a_,b_,c_])6 C$ H0 v; H( V& T
    
11.     st[a_][b_][c_]=1; c& c' s* Q5 W3 o7 M
    
12. def bfs():
    + }  Q( y4 q* L0 m* M1 q4 n. g5 B
13.     q.append([0,0,c])
    ! v* q) C' O\" G  ]% c3 o' [) S. j3 r  Y
14.     st[0][0][c]=1
    ' P- X  _; N/ K
15.     while q:7 J2 R' c2 i/ w5 e
    
16.         a_,b_,c_ = q.popleft()4 a/ C5 v9 d0 B
    
17.         ins( a_-min(a_,b-b_) , b_+min(a_,b-b_) , c_ )
    5 g/ P( [* g' v+ @; r
18.         ins( a_-min(a_,c-c_) , b_ , c_+min(a_,c-c_) )
    # U7 b7 H' z6 a& h
19.         ins( a_+min(b_,a-a_) , b_-min(b_,a-a_) , c_ )5 V, n1 g) o( R% L4 i
    
20.         ins( a_ , b_-min(b_,c-c_) , c_+min(b_,c-c_) )
    1 S: w% `+ J- X  Y5 l) [! D* U
21.         ins( a_+min(c_,a-a_) , b_ , c_-min(c_,a-a_) )  ^7 G* p5 s' z\" g6 e8 K0 C
    
22.         ins( a_ , b_+min(c_,b-b_) , c_-min(c_,b-b_) )5 F4 D  K5 d* X$ R
    
23. bfs()( \/ T8 R' l2 W  p
    
24. for c_ in range(c+1):
    ! R4 v; R9 ], w% o& C
25.     for b_ in range(b+1):
    ; x- i# f1 s0 s- j- N! D' T
26.         if st[0][b_][c_]:! |# m% q8 ~# K& Y; C
    
27.             print(c_,end=' ')0 j! J9 A' P; a3 S$ ~; [
    
28.             break

复制代码

2 T: O. e0 Q/ n; r( K# m