python 解决母亲的奶牛问题

2744557306

题目描述】
& h; ^4 [  n/ d2 p3 h. ]/ l% p
9 a4 t- t, H8 b        农夫约翰有三个容量分别为 A,B,C 升的挤奶桶。最开始桶 A 和桶 B 都是空的，而桶 C 里装满了牛奶。有时，约翰会将牛奶从一个桶倒到另一个桶中，直到被倒入牛奶的桶满了或者倒出牛奶的桶空了为止。这一过程中间不能有任何停顿，并且不会有任何牛奶的浪费。请你编写一个程序判断，当 A 桶是空的时候，C桶中可能包含多少升牛奶，找出所有的可能情况。
+ o( v. }2 r! h8 x: d+ q
" t/ O& k' x. e【输入格式】

0 j+ D" _7 a4 ^# M. M        共一行，包含三个整数 A,B,C。

+ K4 J5 w0 M- q. f1 t0 k【输出格式】

8 i6 M( g% W5 S0 Z6 U2 E, X- K  X        共一行，包含若干个整数，表示 C 桶中牛奶存量的所有可能情况，请将这些数字按升序排列。

0 ~; {5 O1 L  T1 g# I" L【数据范围】
. v- S7 k; A, |3 ~( D% r
5 M0 Y- k3 l8 Y+ D' e( d; h        1≤A,B,C≤20

% d& h- s5 |& }5 ]【输入样例】
/ ?" F) Y- }( e  q% q$ s
8 9 10
9 ~" F9 q* l# ]" b1 \- Q, F, _【输出样例】

1 2 8 9 10
【解题思路】
! n# p/ U) w9 @7 {& ?0 z; L
        BFS简答模拟一下倒牛奶的过程。

1. from collections import *$ h, j$ H8 s) Z
   
2. a,b,c = map(int,input().split())/ o5 p\" L6 W( j
   
3. n = 22
   $ D) _6 B' J0 b+ T  p' s9 X
4. st = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]
   , t# E$ `; p8 {* s
5. 
   2 ^' U; F! N0 E
6. q = deque()5 l7 \8 t+ [/ k! R$ \* T' i
   
7. def ins(a_,b_,c_):/ P\" _# {7 a  |6 _\" U7 g
   
8.     global q
   9 K/ _! b* O1 O% D' y. c+ ~/ E
9.     if st[a_][b_][c_]:return. K4 m  p' g: p
   
10.     q.append([a_,b_,c_])
    + b6 |2 g4 C$ N/ A\" z7 _3 E* C
11.     st[a_][b_][c_]=16 u7 l5 l2 _\" t, r
    
12. def bfs():% m- ?  F7 L1 a, m6 Y+ ?
    
13.     q.append([0,0,c])3 i/ {, m  W: t4 o
    
14.     st[0][0][c]=1
    # }. e; B  ]8 \# P4 K, B
15.     while q:
    ' Q0 [% y# K5 C$ U  ]
16.         a_,b_,c_ = q.popleft()
    / k# k! K! H- W
17.         ins( a_-min(a_,b-b_) , b_+min(a_,b-b_) , c_ )
    - L9 A5 O+ e\" _% A
18.         ins( a_-min(a_,c-c_) , b_ , c_+min(a_,c-c_) )
    4 ?; T! \/ p7 q
19.         ins( a_+min(b_,a-a_) , b_-min(b_,a-a_) , c_ )4 K; m6 ?\" y1 Y0 h, J+ R
    
20.         ins( a_ , b_-min(b_,c-c_) , c_+min(b_,c-c_) )
    & d5 h6 M: J/ [' W
21.         ins( a_+min(c_,a-a_) , b_ , c_-min(c_,a-a_) )7 V2 z! m  Q7 t: A
    
22.         ins( a_ , b_+min(c_,b-b_) , c_-min(c_,b-b_) )
    ! n, ~9 |7 E' W4 f  a  O; h
23. bfs()
    5 l- H, _7 T5 A6 V
24. for c_ in range(c+1):
    : {) I3 X) p8 S+ S% i* }
25.     for b_ in range(b+1):
    ! N7 O* T0 h) p8 k
26.         if st[0][b_][c_]:
    * u2 B6 J: W6 C\" L, Y
27.             print(c_,end=' ')3 K7 m$ ]% j) S$ M9 H( i! U; W0 R
    
28.             break

复制代码

- ]/ i$ u, B0 o7 O2 u& M