python 解决母亲的奶牛问题

2744557306

题目描述】

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

【输入格式】
" o& v' ^1 \+ ~5 e* q( ~2 D, a8 p
        共一行，包含三个整数 A,B,C。
& ~1 }+ J; ~/ v, A' u
【输出格式】

1 c4 @; L0 V: `. |7 W: H" s        共一行，包含若干个整数，表示 C 桶中牛奶存量的所有可能情况，请将这些数字按升序排列。

【数据范围】

        1≤A,B,C≤20

' K; a. L1 ^; o  v5 ^: U5 Y【输入样例】
0 Y& _9 k% L2 k% }( e: S: J4 j
) q- D- @# F+ J% L+ Y+ o8 9 10
【输出样例】
! |: h+ Z1 k! A0 A- A  N4 f7 H
1 2 8 9 10
  Q0 v- Q4 n& z8 p& _: d 【解题思路】

5 i2 u/ Q( `- [# B; F2 q        BFS简答模拟一下倒牛奶的过程。

1. from collections import *+ h3 E8 j( M  p6 q
   
2. a,b,c = map(int,input().split())
   0 S  c9 I( M8 `) ~
3. n = 22
   1 I* c/ `$ c7 k; ~
4. st = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]7 F/ [# `& T9 ]- C* W* w% X9 Z
   
5. 
   , t; O7 d% m6 _8 A/ r- y
6. q = deque()/ u& j! A; V) ?* U3 a) l
   
7. def ins(a_,b_,c_):: L: a7 O0 p% g5 i) U9 _8 n
   
8.     global q: B  t0 `# F7 n! m
   
9.     if st[a_][b_][c_]:return# |: d# y2 _2 M0 T# M) s3 q$ F
   
10.     q.append([a_,b_,c_])
    2 S7 O& ?, B. |. F; A$ X/ n8 a
11.     st[a_][b_][c_]=1
    ) r8 E1 Z/ M- C\" M+ _
12. def bfs():
    5 ?1 q\" Y- i8 L1 t) K
13.     q.append([0,0,c])* D0 Y6 Y1 f/ n( C% j; A
    
14.     st[0][0][c]=10 Y$ _( w& J7 y1 q9 k- g\" T2 d
    
15.     while q:) I% F\" n2 k. I, I1 u
    
16.         a_,b_,c_ = q.popleft()6 B$ w! o5 z: r4 j
    
17.         ins( a_-min(a_,b-b_) , b_+min(a_,b-b_) , c_ )
    & M5 W, w, D* E! ~; f\" y+ P
18.         ins( a_-min(a_,c-c_) , b_ , c_+min(a_,c-c_) ); K. a% w% w1 w+ k
    
19.         ins( a_+min(b_,a-a_) , b_-min(b_,a-a_) , c_ ). }7 X! f6 T: i$ f* }
    
20.         ins( a_ , b_-min(b_,c-c_) , c_+min(b_,c-c_) )* o\" H0 G( V1 c  |/ b, S3 ~
    
21.         ins( a_+min(c_,a-a_) , b_ , c_-min(c_,a-a_) )
    : N% k' a3 A$ {2 Z1 u( b
22.         ins( a_ , b_+min(c_,b-b_) , c_-min(c_,b-b_) )% ^0 t. \$ K0 P! P6 p9 B3 E
    
23. bfs()
    9 k. O3 ~9 U$ v
24. for c_ in range(c+1):7 h3 m1 M9 e2 d& D; c
    
25.     for b_ in range(b+1):
    ( e# A* i: J' R9 ~! V
26.         if st[0][b_][c_]:
    % b+ b. I9 Y. M' J+ I
27.             print(c_,end=' ')
    ) S\" v! F9 B5 F8 }1 m\" W
28.             break

复制代码

$ {1 Z3 T$ ?! a