#鱼C五周年嘉年华#算法——送(qiang)快(jiang)递(pin)。--已经结束

d5zhao

看看！！！

zd0307

谢谢lz的帖子，挣鱼币

zd0307

7ocx

zd0307

好像很难得样子

zd0307

谢谢lz给鱼币

woshidamowang24

好难啊还有小甲鱼送？

笑脸对世界

我是来捧场的

笑脸对世界

我来捧场的

戴宇轩

@wei_Y 最近学算法，看到广度优先搜索，猛然想到这个题目
对于迷宫最短路径来说，广度优先再合适不过了，广度优先不像深度那样找到所有路径，而是从起点一层层地向终点推进，效率惊人...

1. from queue import Queue
   
2. 
   
3. # 定义四个方向
   
4. di = (1, 0, -1, 0)
   
5. dj = (0, 1, 0, -1)
   
6. name = 'DRUL'
   
7. 
   
8. 
   
9. '用广度优先搜索算法找两点间最短路径'
   
10. # 返回值: 完整的路径, 例如: 'RULDDRD'
    
11. # 起点坐标: (sx, sy)
    
12. # 终点坐标: (ex, ey)
    
13. def minimum(sx, sy, ex, ey):
    
14.     passed = [[0] * M for i in range(N)]
    
15.     passed[sx][sy] = ''
    
16.     que = Queue()
    
17.     que.put((sx, sy))
    
18.     x, y = -1, -1
    
19.     while x != ex or y != ey:
    
20.         x, y = que.get()
    
21.         for i, j, n in zip(di, dj, name):
    
22.             nx, ny = x + i, y + j
    
23.             if 0 <= nx < N and 0 <= ny < M and passed[nx][ny] == 0 and maze[nx][ny] != 'W':
    
24.                 passed[nx][ny] = '%s%s' % (passed[x][y], n)
    
25.                 que.put((nx, ny))
    
26.     return passed[ex][ey]
    
27. 
    
28. 
    
29. # maze:   迷宫
    
30. # N:      迷宫高度
    
31. # M:      迷宫宽度
    
32. # ups:    加速器位置(列表)
    
33. # path:   最短路径
    
34. # length: 最短路径长度
    
35. def maps(data):
    
36.     # 初始化迷宫, 设置高和宽
    
37.     global maze, N, M
    
38.     maze = [list(i) for i in data]
    
39.     N = len(maze)
    
40.     M = len(maze[0])
    
41. 
    
42.     ups = []
    
43. 
    
44.     for x in range(N):
    
45.         for y in range(M):
    
46.             if maze[x][y] == 'B':
    
47.                 ups.append((x, y))
    
48.             elif maze[x][y] == 'S':
    
49.                 sx, sy = x, y
    
50.             elif maze[x][y] == 'E':
    
51.                 ex, ey = x, y
    
52. 
    
53.     # 先走一遍不经过加速器的路线
    
54.     path = minimum(sx, sy, ex, ey)
    
55.     length = len(path) * 2
    
56. 
    
57.     # 对任意两个加速器, 判断 "先从起点走到第一个加速器, 加速, 从第一个加速器走到第二个加速器, 停止加速, 从第二个加速器走到终点" 的路径是否比原先的路径短. 如果是, 那么替换原先的路径长度和路径
    
58.     for i in ups:
    
59.         for j in ups:
    
60.             a = minimum(sx, sy, *i)
    
61.             b = minimum(*i, *j)
    
62.             c = minimum(*j, ex, ey)
    
63.             new_l = (len(a) + len(c) + 1) * 2 + len(b)
    
64.             if new_l < length:
    
65.                 length = new_l
    
66.                 path = '%sB%sB%s' % (a, b, c)
    
67. 
    
68.     return (path, length)
    
69. 
    
70. 
    
71. #####################################
    
72. 
    
73. 
    
74. data0 = ['S.....', '......', '......', '......', '......', '.....E']
    
75. data1 = ['S...', '....', 'B.WB', '..WE']
    
76. data2 = ['S...', '....', 'B..B', '..WE']
    
77. data3 = ['S.BB.E']
    
78. data4 = ['S.W...', '..WB..', '..WW..', '....B.', '....W.', '..B.BE']
    
79. data5 = ['SBW...', '.WWB..', '..WW..', '......', '...WW.', '..BWBE']
    
80. data6 = ['S..BW.', '.WWWWW', '.W....', '.W.W.B', '.W.W..', '...W.E']
    
81. data7 = ['EBW.S.', '.WWB..', '..WW..', '......', '...WW.', '..BWB.']
    
82. data8 = ['S..BW.....', '.WWWWWW...', '.WBW......', '.W.W.BW...', '.W.W..WWW.', '...W..W...', '......W...', '.WWWW.W..B', '..........', '.....B..BE']
    
83. data9 = ['S.........', '..........', '..........', '..........', '..........', '..........', '..........', '..........', '..........', '.........E']
    
84. 
    
85. for i in range(10):
    
86.     data = eval('data%d' % (i,))
    
87.     print('地图:\n        %s\n\n最短路径: %s\n路径长度: %d\n%s' % ('\n        '.join(data), *maps(data), '=' * 36))

复制代码

wei_Y

戴宇轩 发表于 2017-5-25 00:35
@wei_Y 最近学算法，看到广度优先搜索，猛然想到这个题目
对于迷宫最短路径来说，广度优先再合适不过了， ...

好久不见，这是要回归的节奏呀。