python小练习（065）：探索法（广度优先搜索）30行代码求解倒酒问题

水煮小小鱼

BFS算法的Python实现

孤独的林

学习

nlyh

学习学习 看看代码

WelanceLee

1. def xdd(arr, r):
   
2.     if r not in arr:
   
3.         arr.append(r)
   
4.         action[r] = arr[index]
   
5.     return arr
   
6. 
   
7. start = (0, 0)
   
8. queue = [start]
   
9. action = {}
   
10. index = 0
    
11. while True:
    
12.     q = queue[index]
    
13.     if q[0] == 2 or q[1] == 2:
    
14.         break
    
15.     xdd(queue, (7, q[1]))
    
16.     xdd(queue, (0, q[1]))
    
17.     xdd(queue, (q[0], 0))
    
18.     xdd(queue, (q[0], 11))
    
19.     x = q[0] + q[1]
    
20.     if x <= 7:
    
21.         xdd(queue, (x, 0))
    
22.         xdd(queue, (0, x))
    
23.     if 7 < x < 11:
    
24.         xdd(queue, (7, x - 7))
    
25.         xdd(queue, (0, x))
    
26.     if x >= 11:
    
27.         xdd(queue, (x - 11, 11))
    
28.         xdd(queue, (7, x - 7))
    
29.     index += 1
    
30. 
    
31. solution = [(0,0)]
    
32. while q != (0, 0):
    
33.     solution.insert(1, q)
    
34.     q = action[q]
    
35. 
    
36. for each in solution:
    
37.     print(each)
    
38.    

复制代码

没用pop，直接在queue里面看状态是不是走过

qaz123765

来看下程序

yhe0924

学习下BFS 搞不懂头疼极了

Castieler

1

joeyzhong

感谢分享，真需要

聂路成

学习

tianduan18

求答案~

昨日已化成烟

采用迭代判断进行计算吗？

兢兢

上酒

hszzjs

学习学习！！

yyf900524

回复看源码

mahaweilu

nice

shigure_takimi

JAY饭

这个题确实想不出广度探索法的需求，因为我试了一下都是直线型的思路，所以：

1. m,n = 7,11
   
2. visit = []
   
3. 
   
4. def move(a,b,m,n):
   
5.    
   
6.     if a == 0:
   
7.         if b == 0:
   
8.             a += m
   
9.         elif b != 0 and b != n:
   
10.             a += m
    
11.         else:
    
12.             return None
    
13.         
    
14.     elif a == m:
    
15.         if b == 0:
    
16.             t = n-b
    
17.             if t <= a:
    
18.                 a -= t
    
19.                 b += t
    
20.             else:
    
21.                 b += a
    
22.                 a = 0
    
23.                
    
24.         elif b != 0 and b != n:
    
25.             t = n-b
    
26.             if t <= a:
    
27.                 a -= t
    
28.                 b +=t
    
29.             elif t > a:
    
30.                 b += a
    
31.                 a = 0
    
32. 
    
33.     elif a != 0 and a != m:
    
34.         if b == n:
    
35.             b=0
    
36.         elif b == 0:
    
37.             t = (n-b)
    
38.             if t <= a:
    
39.                 a -= t
    
40.                 b +=t
    
41.             elif t > a:
    
42.                 b += a
    
43.                 a = 0
    
44. 
    
45.    
    
46.     print(a,b)
    
47.     return a,b
    
48. a,b,c = 0,0,1
    
49. a1,b1,c1 =0,0,1
    
50. while c:
    
51.     (a,b) = move(a,b,7,11)
    
52.     if a ==2 or b ==2:
    
53.         print('用了%d步'%c)
    
54.         break
    
55.     c += 1
    
56. while c1:
    
57.     (a1,b1) = move(a1,b1,11,7)
    
58.     if a1 ==2 or b1 ==2:
    
59.         print('用了%d步'%c1)
    
60.         break
    
61.     c1 += 1

复制代码

Hank_

xiaozheasd123

后来还开了个v客户管理客户