python 解决母亲的奶牛问题

2744557306

题目描述】

        农夫约翰有三个容量分别为 A,B,C 升的挤奶桶。最开始桶 A 和桶 B 都是空的，而桶 C 里装满了牛奶。有时，约翰会将牛奶从一个桶倒到另一个桶中，直到被倒入牛奶的桶满了或者倒出牛奶的桶空了为止。这一过程中间不能有任何停顿，并且不会有任何牛奶的浪费。请你编写一个程序判断，当 A 桶是空的时候，C桶中可能包含多少升牛奶，找出所有的可能情况。
5 r- H; o1 n. u; E/ V" R
【输入格式】
: }; i8 V9 h! a$ z" F4 G
1 h- }3 D/ M8 W- |/ ^0 D        共一行，包含三个整数 A,B,C。
5 {, _) d7 s3 m; ^# a0 k; F
* Y! I$ K, c) e* W【输出格式】

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

【数据范围】
3 o' C4 [5 g( R% C5 i
        1≤A,B,C≤20

4 ^, J5 p6 e4 p【输入样例】
7 U; ~; j) @* N* k* a
8 9 10
! G- E+ n% x! Z' G. b9 @' `$ ~【输出样例】
" \" Q7 U$ g. \& R2 `! {
# _& v* d% L7 ~' a# V( i: g1 2 8 9 10
/ A' v' F9 o& p  O! t 【解题思路】

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

1. from collections import *) G\" q! ~; @  v: n0 h
   
2. a,b,c = map(int,input().split())
   : z/ K$ k9 A: I  y# J
3. n = 22
   4 B. X+ e2 _* t! c& b
4. st = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]! U5 d* L; n- N0 z' ^
   
5. : R% c! D: D) P- M- K
   
6. q = deque()
   ) b( w* b6 u# I
7. def ins(a_,b_,c_):
   + K( K% }  p/ Q; \
8.     global q- X+ W7 D: l0 G\" O1 R
   
9.     if st[a_][b_][c_]:return
   1 K& N3 b( s- v3 W- f
10.     q.append([a_,b_,c_])
    1 K+ I8 f9 C/ B* ^1 o# p
11.     st[a_][b_][c_]=1/ H2 W& N% u/ x& M* |
    
12. def bfs():: I; \- A8 h; M
    
13.     q.append([0,0,c])
    8 a9 ^( w' N2 L. r% H3 m1 h) {
14.     st[0][0][c]=1
    $ W* q' A: P6 r+ m! R: t$ Y
15.     while q:4 g( g) ~0 O, M) ?* P
    
16.         a_,b_,c_ = q.popleft()9 E9 Z+ d, C2 o0 C: [. v
    
17.         ins( a_-min(a_,b-b_) , b_+min(a_,b-b_) , c_ )
    + n4 B# \# g( F7 W4 ^
18.         ins( a_-min(a_,c-c_) , b_ , c_+min(a_,c-c_) )3 c6 W8 H0 d$ P0 I  P+ @2 `
    
19.         ins( a_+min(b_,a-a_) , b_-min(b_,a-a_) , c_ )
    4 u4 w) h\" d  P# N- [5 T5 f& a
20.         ins( a_ , b_-min(b_,c-c_) , c_+min(b_,c-c_) )6 e$ P+ g+ D: s1 H5 I
    
21.         ins( a_+min(c_,a-a_) , b_ , c_-min(c_,a-a_) )9 w  L, I( ~\" }
    
22.         ins( a_ , b_+min(c_,b-b_) , c_-min(c_,b-b_) )
    & z8 I+ D0 n+ Q% b
23. bfs()
    # j$ g0 T1 B/ p( t# L2 z
24. for c_ in range(c+1):
    7 m& ^% n+ J5 a6 X
25.     for b_ in range(b+1):
    ; E. }- C1 Y0 N# y* i4 w2 @
26.         if st[0][b_][c_]:' T0 b& O* I5 D& j$ s$ X, d
    
27.             print(c_,end=' ')
    $ F7 M( |) {) N/ l* c\" o
28.             break

复制代码