python 解决母亲的奶牛问题

2744557306

题目描述】
. r# W4 k1 H2 Y3 {7 r4 y, I
; b5 b* [8 b3 V7 h$ `        农夫约翰有三个容量分别为 A,B,C 升的挤奶桶。最开始桶 A 和桶 B 都是空的，而桶 C 里装满了牛奶。有时，约翰会将牛奶从一个桶倒到另一个桶中，直到被倒入牛奶的桶满了或者倒出牛奶的桶空了为止。这一过程中间不能有任何停顿，并且不会有任何牛奶的浪费。请你编写一个程序判断，当 A 桶是空的时候，C桶中可能包含多少升牛奶，找出所有的可能情况。

【输入格式】

4 n" e; p  T' ~( v1 y/ \& }* m        共一行，包含三个整数 A,B,C。
7 @6 \! A) U  p7 N
  i& ?: n) h$ N- j! t7 o【输出格式】
5 l" F% U/ q1 }6 N* Q' U
9 D- m+ ~( }9 f/ v5 F        共一行，包含若干个整数，表示 C 桶中牛奶存量的所有可能情况，请将这些数字按升序排列。
; p" p! c( }- E( L4 t; N
# \" c" \8 B9 C% b9 r1 n4 D【数据范围】
" E: l& F) V" c6 P# l" U
6 b& v/ e. [9 E+ n5 D        1≤A,B,C≤20

【输入样例】
% M$ @  B4 ^/ {- ~( u- {7 [" G
8 9 10
【输出样例】
1 a, s' E& A% \4 c: }
8 n& u8 r( _' d3 u& p! N1 2 8 9 10
% c7 k- Q1 A; E+ s+ v/ s 【解题思路】

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

1. from collections import *3 c' T3 a4 Z* I7 V# }+ p
   
2. a,b,c = map(int,input().split())
   / c& J6 t  y1 {8 b3 J9 o5 w/ D
3. n = 22' B, N! A, d. C. E. ]( y+ g
   
4. st = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]
   ' g) ~. F% s2 r; R9 a' ~2 I
5. 
   / b8 O, c, i- J/ z5 e
6. q = deque()+ _: J' p  e1 [/ p
   
7. def ins(a_,b_,c_):2 K; X6 j: y, }% J& ~
   
8.     global q: y9 u: C. O9 L( y) Y8 ^: e
   
9.     if st[a_][b_][c_]:return8 S- o) M* P3 V\" o
   
10.     q.append([a_,b_,c_])
    # N! r# l. N$ @* M
11.     st[a_][b_][c_]=1- I4 J: t& ]+ d% @& O: U
    
12. def bfs():8 w) m6 w  V3 E
    
13.     q.append([0,0,c])
    9 F; x3 ^# K/ d: L8 a5 \. [! `7 Q7 \
14.     st[0][0][c]=1: o% e% D4 I/ g* m3 O! z
    
15.     while q:' S: g  y( n6 t9 i) l
    
16.         a_,b_,c_ = q.popleft()/ J0 e( b0 N$ S5 i
    
17.         ins( a_-min(a_,b-b_) , b_+min(a_,b-b_) , c_ )
    ' @) w; H) r) m3 L) `2 B
18.         ins( a_-min(a_,c-c_) , b_ , c_+min(a_,c-c_) )% U; I% j+ e. Q4 k. w5 q4 B
    
19.         ins( a_+min(b_,a-a_) , b_-min(b_,a-a_) , c_ )
    1 g4 \. x/ ^( z9 y
20.         ins( a_ , b_-min(b_,c-c_) , c_+min(b_,c-c_) )4 {6 |) V' m& N: V
    
21.         ins( a_+min(c_,a-a_) , b_ , c_-min(c_,a-a_) )
    $ ]: v- a, N8 Y
22.         ins( a_ , b_+min(c_,b-b_) , c_-min(c_,b-b_) )7 a& i4 W* O* R$ _6 @/ v
    
23. bfs(), ~* T3 }, k+ K0 K0 U
    
24. for c_ in range(c+1):
    8 z4 w2 t  O& q( n
25.     for b_ in range(b+1):
    % G  E8 S: N' v* M
26.         if st[0][b_][c_]:4 c. X; X& ^2 W# A# I
    
27.             print(c_,end=' ')- A5 Y) m  o; R5 F# k
    
28.             break

复制代码