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

wei_Y

故事背景:
在一个伸手不见五指滴黑夜~，有一只正在给你送

小甲鱼公仔的快递小哥。

到了你家门口，砰砰砰敲着门，幽幽的说着:

"what！这么快！？"
"那是，我可是get到新技能了。"
---故事结束，之后发生的事件略凶残！---

OK，这次的任务就是帮助快递小哥找到送货可以的最短时间！(什么，居然不是最短路径。)

基本介绍

1. S表示起点
   
2. E表示终点
   
3. W表示水
   
4. B进出加速状态。(进入后需退出。)
   
5. 非加速状态下移动(URLD)耗时为2.
   
6. 加速状态下移动(URLD)耗时为1.
   
7. 进出加速状态耗时为1.

复制代码

"U" -- Up (北)
"D" -- Down (南)
"L" -- Left (西)
"R" -- Right (东)
"B" -- 进出加速模式。
输入:  一个字符串列表地图。
输出:  一个带路径的字符串。

------------------------------------------------

详细说明:
从起点(S)开始，每次只可以移动一步(上(U)下(D)左(L)右(R))，到达终点(E)结束。到达E时若是加速状态则不可以算完成必须退出加速状态。
水(W)不可以通过，任何状态下都不可以。起点(S)与终点(E)总是分布在地图的左上角(0,0)和右下角.地图最小为1x1,最大为6x6.地图的形式如栗子中所示。经过B可以选择加速or不加速。
需要完成的任务是找到从起点(S)开始到终点(E)的最短时间的走法(可能不唯一)。
最终以函数形式提交，若有多个函数请注明调用哪一个函数。
最终返回最短时间路径的走法。



栗子:


怎么走无所谓只要时间符合就OK。

maps(["S...","....","B.WB","..WE"])

1. ["S...",
   
2. "....",
   
3. "B.WB",
   
4. "..WE]

复制代码

#RRRDDD
最低耗时: 12
--------------------------------

maps(["S...","....","B..B","..WE"])

1. ["S...",
   
2. "....",
   
3. "B..B",
   
4. "..WE"]

复制代码

#DDBRRRBD  
最低耗时: 11

1. >>> maps(["S...","....","B.WB","..WE"])
   
2. 'DRRRDD'
   
3. >>> maps(["S...","....","B..B","..WE"])
   
4. 'DDBRRRBD'

复制代码

地图最大6*6。
测试:
["S.BB.E"] "RRRRR"
["S.W...","..WB..","..WW..","....B.","....W.","..B.BE"]  "DDDDDRRBRRBR"
["SBW...",".WWB..","..WW..","......","...WW.","..BWBE"]  "RBLDDDRRRRRDDLBR"
["S..BW.",".WWWWW",".W....",".W.W.B",".W.W..","...W.E"]  'RRRBLLLDDDDDRRUUURRDRBDD'

自己测试或者让我测试都可以哦。通过3个即算完成。


-----------------------
要求:
无任何要求，第三方库最好能提供一下下载地址，自写的模块一起把代码贴上(附上一个#模块名    的注释)或随附件上传。


排名:
高效，可读性高(不要吝啬注释)。若1分钟还不出则失败。(那个，呃……我电脑渣你懂得~)

-----------------------
奖品及换奖品的方式请在此帖查看
http://bbs.fishc.com/forum.php?mod=viewthread&tid=57807&page=1#pid2265719

哦对了，可在此查看一下普通迷宫思路。内有大神的答案，无视我写的吧。
-----------------------------本活动最终解释权归 介哥 and weiy所有！---------------------



P.S没懂得鱼油能不能说一下哪个地方呢?就说个没懂我也不知道该怎么改。。

戴宇轩

成品 12
版本: Python 3.4.0a0

1. import re #分开路径用
   
2. import sys #报错用
   
3. class Go_to_B: #向加速器移动的类
   
4.     def __init__(self, direction, opposite): #要传入四个方向和相反路径字典
   
5.         self.result = [] #结果存放处
   
6.         self.direction = direction #方向存放处
   
7.         self.opposite = opposite #相反路径字典
   
8.     def __call__(self, path, field, history): #被调用时
   
9.         (x, y) = history[-1] #找到现在位置
   
10.         if field[x][y] == 'B': #如果找到了加速器
    
11.             self.result.append(path) #结果增加这条路径
    
12.             del history[-1];return 0 #推向前一个点, 向其他方向继续寻找
    
13.         for i in self.direction: #搜索四个方向
    
14.             (x, y) = (history[-1][0] + i[0], history[-1][1] + i[1]) #假定向这个方向移动1格
    
15.             if not ((x, y) in history or field[x][y] == 'W'): #如果超出边界 or 走过这个点(非递归造成) or 前面被水挡住了, 就搜索另一个方向
    
16.                 history+=[(x, y)] #如果前面是通路, 将这个点加入history, 下次递归就从这个点开始
    
17.                 self(path + i[2], field, history) #递归
    
18.         del history[-1] #如果找到一条死路(再找就回去了), 就回到上一个点, 继续寻找
    
19.     def __str__(self): #被str()时
    
20.         self.result.sort(key = len) #找到最短的一条路
    
21.         temp = self.result and self.result[0] or '' #如果整个迷宫里没有加速器, 开头结尾路径为空
    
22.         return temp + (temp and 'B' or '') + ''.join([self.opposite[i] for i in temp[::-1]]) #并返回
    
23. def fix(path): #用来消除路径中的[RL|LR|UD|DU|BB]
    
24.     while path.replace('LR', '').replace('RL', '').replace('UD', '').replace('DU', '').replace('BB', '') != path:
    
25.         path = path.replace('LR', '').replace('RL', '').replace('UD', '').replace('DU', '').replace('BB', '')
    
26.     return path
    
27. def checkroute(data): #主函数
    
28.     direction = ((0, 1, 'R'), (1, 0, 'D'), (-1, 0, 'U'), (0, -1, 'L')) #定义四个方向
    
29.     data = ['W' * (len(data[0]) + 2)] + ['W' + i + 'W' for i in data] + ['W' * (len(data[-1]) + 2)] #给迷宫加上墙壁
    
30.     opposite = {'R': 'L', 'U': 'D', 'D': 'U', 'L': 'R'} #相反路径字典
    
31.     (start_path, end_path) = ([], []) #开始和结束到加速器的最短距离
    
32.     (S_axis, E_axis) = ([], [])
    
33.     ##### 这个函数段用于找到S和E的坐标
    
34.     x = 0
    
35.     for i in data:
    
36.         y = 0
    
37.         for j in i:
    
38.             if j == 'S':S_axis.append((x, y))
    
39.             if j == 'E':E_axis.append((x, y))
    
40.             y += 1
    
41.         x += 1
    
42.     ##### 结束
    
43.     ##### 判断起点, 终点个数是否正确
    
44.     if len(S_axis) != 1:sys.exit('起点个数不正确!')
    
45.     if len(E_axis) != 1:sys.exit('终点个数不正确!')
    
46.     ##### 结束
    
47.     def view_all_path(data): #这个函数用来找到所有路径(不兜圈)
    
48.         result = [] #结果路径存放处
    
49.         ########## 这个脚本段用来记录起点和终点到加速器后返回的最短距离
    
50.         start_path_temp = Go_to_B(direction, opposite)
    
51.         start_path_temp('', data, S_axis[:]) #因为Move_to_B()()会把S_axis删光, 浅拷贝一次
    
52.         start_path.append(str(start_path_temp))
    
53.         end_path_temp = Go_to_B(direction, opposite)
    
54.         end_path_temp('', data, E_axis)
    
55.         end_path.append(str(end_path_temp))
    
56.         ########## 结束
    
57.         def serach(path, field, history): #搜索函数
    
58.             (x, y) = history[-1] #找到现在位置
    
59.             if field[x][y] == 'E': #如果找到了终点
    
60.                 result.append(path) #结果增加这条路径
    
61.                 del history[-1];return 0 #推向前一个点, 向其他方向继续寻找
    
62.             for i in direction: #搜索四个方向
    
63.                 (x, y) = (history[-1][0] + i[0], history[-1][1] + i[1]) #假定向这个方向移动1格
    
64.                 if not ((x, y) in history or field[x][y] == 'W'): #如果超出边界 or 走过这个点(非递归造成) or 前面被水挡住了, 就搜索另一个方向
    
65.                     history+=[(x, y)] #如果前面是通路, 将这个点加入history, 下次递归就从这个点开始
    
66.                     serach(path + i[2] + ('B' if field[x][y] == 'B' else ''), field, history) #递归
    
67.             del history[-1] #如果找到一条死路(再找就回去了), 就回到上一个点, 继续寻找
    
68.         serach('', data, S_axis) #搜索, 此时路径为空, 传入起点位置
    
69.         return result #将找到的所有路径返回
    
70.         ###### 寻找路径函数结束
    
71.     raw_path = view_all_path(data) #得到只走一次的路径, 传入迷宫
    
72.     factored_path = [] #所有(含开头结尾加速器)路径存放处
    
73.     start_path = start_path[0] #开头加速器路径
    
74.     end_path = end_path[0] #结尾加速器路径
    
75.     final_path = [] #最终路径
    
76.     least = {} #时间与路径的字典
    
77.     for i in raw_path: #一共有四种路径(原路径, 开头加速器 + 原路径, 原路径 + 结尾加速器, 开头加速器 + 原路径 + 结尾加速器)
    
78.         factored_path += [i, start_path + i, i + end_path, start_path + i + end_path]
    
79.     for i in [fix(i) for i in factored_path]: #逐个查看消除重复路径后的路径
    
80.         if i.count('B') in (0, 2): #如果有0个或2个B在路径内
    
81.             final_path.append(i) #直接放入正确路径
    
82.         elif i.count('B') > 2: #如果有多于两个B, 仅保留最前和最后的B(这样时间少)
    
83.             frount = i.index('B') + 1
    
84.             back = len(i) - i[::-1].index('B') - 1
    
85.             final_path.append(i[:frount] + i[frount:back].replace('B', '') + i[back - 1:])
    
86.         final_path.append(i.replace('B', '')) #再加入一个全程不加速的路径(以上判断皆通过此处)
    
87.     for i in final_path: #查看所有正确路径
    
88.         all_time = 0 #每条路径时间一开始是0
    
89.         split_path = re.findall('[URLD]+(?=B)|B[URLD]+B|(?<=B)[URLD]+|[URLD]+', i) #用正则表达式将路径分开, 如下
    
90.         #例子: 'RRRRRBUUUBLLL'   ------>   ['RRRRR', 'BUUUB', 'LLL']
    
91.         for j in split_path: #逐个查看所有分开路径
    
92.             if j[0] == 'B': #如果处于加速状态
    
93.                 all_time += len(j) #时间和加上加速后的路径长度(单位: 1)
    
94.             else: #否则(非加速状态)
    
95.                 all_time += len(j) * 2 #时间和加上现在路径的总长度(单位: 2)
    
96.         least[all_time] = i #least的现在总时间对应现在的路径
    
97.     print('最短时间: %s 路径:' % min(least), least[min(least)]) #输出最短的时间和对应的路径, Done!
    
98. # -*- -*- -*- -*- -*- # 测试数据
    
99. No_1 = ["SBW...",".WWB..","..WW..","......","...WW.","..BWBE"]
    
100. No_2 = ["S..BW.",".WWWWW",".W....",".W.W.B",".W.W..","...W.E"]
     
101. checkroute(No_1)
     
102. checkroute(No_2)

复制代码

挥舞乾坤

完整版,测试了所有版主提供的路径,并可以实现10*10,支持随机起点和终点,再大的就没有测试了,欢迎测试,鉴于之前版本因为寻路全部由递归完成(递归遍历所有路径真是个大工程)耗时太久,所以又出了这个版本!

1. import copy
   
2. 
   
3. #找到指定地图中,两点之间的最短路径
   
4. def maze(data, p1, p2):
   
5.     'data:迷宫数据,p1:起点,p2终点'
   
6.    
   
7.     rows = len(data) # 地图行数
   
8.     column = len(data[0]) #地图列数
   
9.     result = [] # 可达路径列表
   
10.     x, y = p1
    
11. 
    
12.     # fx可移动的方向
    
13.     fx = [[0, 1, 'R'], [1, 0, 'D'], [0, -1, 'L'], [-1, 0, 'U']]
    
14. 
    
15.     #递归找到最短路径,添加到result列表中
    
16.     def move(path, x, y, maps):
    
17.         'path:存放方向字串,x,y:行,列坐标,maps:迷宫地图'
    
18.         maps[x][y] = 'W' #记录走过的点,防止重复
    
19.         if (x, y) == p2:
    
20.             result.append(path) #如果当前坐标等于终点坐标,把路径添加到列表
    
21. 
    
22.          #在方向列表中逐个尝试移动   
    
23.         for i in fx[:]:
    
24.             if not (0 <= x + i[0] < rows) or not (0 <= y + i[1] < column):
    
25.                 continue
    
26.             if maps[x + i[0]][y + i[1]] in '.SBE':
    
27.                 move('%s%s' % (path,i[2]), x + i[0], y + i[1], maps)
    
28. 
    
29.     fx_ = re_move(fx) #fx_是一个存放所有方向排列组合的生成器,一共24种组合
    
30. 
    
31.     #根据不同的方向排列组合循环调用move,每调用一次添加一个可达路径
    
32.     for each in fx_:
    
33.         fx = each
    
34.         move('', x, y, copy.deepcopy(data))
    
35. 
    
36.      #返回最短的路径   
    
37.     result = {len(x):x for x in result}
    
38.     return result[min(result)]
    
39. 
    
40. #生成方向的排列组合,返回一个生成器
    
41. def re_move(fx):
    
42.     for pos1 in fx:
    
43.         for pos2 in fx:
    
44.             if pos2 == pos1:continue
    
45.             for pos3 in fx:
    
46.                 if pos3 in(pos1,pos2):continue
    
47.                 for pos4 in fx:
    
48.                     if pos4 in(pos1,pos2,pos3):continue
    
49.                     yield([pos1,pos2,pos3,pos4])
    
50. 
    
51. #找到指定字符在地图中的位置,返回一个坐标列表                           
    
52. def find_items(data,item):
    
53.     'data:地图数据,item:要找的字符'
    
54.     result = []
    
55.     for x,each_row in enumerate(data):
    
56.         for y,each_str in enumerate(each_row):
    
57.             if each_str == item:
    
58.                 result.append((x,y))
    
59.     return result
    
60. 
    
61. #找到包含加速的路径,返回一个路径列表
    
62. def spend_path(data, s, e, blist):
    
63.     'data:地图数据,s:起点,e:终点,blist:所有加速点的列表'
    
64.     result = []
    
65. 
    
66.     #循环组合出所有加速路径
    
67.     for each in blist:
    
68.         for other in blist:
    
69.             if each == other:continue
    
70.             path = ''
    
71.             part1 = maze(data, s, each)
    
72.             part2 = maze(data, each, other)
    
73.             part3 = maze(data, other, e)
    
74.             path = '%s%s%s%s%s' % (part1, 'B', part2, 'B', part3)
    
75.             result.append(path)
    
76.     return result
    
77. 
    
78. 
    
79. #计算最短路径,返回一个最短的耗时,和最短路径的字典
    
80. def calc_time(path_list):
    
81.     'path_list:路径列表'
    
82.     result = {}
    
83.     spend = False
    
84.     for each_path in path_list:
    
85.         count = 0
    
86.         for each_char in each_path:
    
87.             if each_char == 'B':
    
88.                 spend = not spend
    
89.                 count += 1
    
90.                 continue
    
91.             sep = 1 if spend else 2
    
92.             count += sep
    
93.         result.update({count:each_path})
    
94.     return min(result),result
    
95.             
    
96.         
    
97.    
    
98. #主函数了     
    
99. def maps(data):
    
100.     data = [list(e.upper()) for e in data]
     
101.     rows = len(data)
     
102.     column = len(data[0])
     
103.     for each in data:
     
104.         print(each)
     
105. 
     
106.     path_list = []
     
107.     S = find_items(data,'S')[0] #找起点
     
108.     E = find_items(data,'E')[0] #找终点
     
109.     B_list = find_items(data,'B') #找所有加速点
     
110. 
     
111.     #加速点大余1个,path_list 获得所有加速路径
     
112.     if len(B_list) > 1:
     
113.         path_list = spend_path(data, S, E, B_list)
     
114. 
     
115.     #加入起点到终点,不走加速的路径
     
116.     path_list.append(maze(data, S, E))
     
117. 
     
118.     #计算所有路径耗时,min_time最小耗时,min_path最短路径
     
119.     min_time,min_path = calc_time(path_list)
     
120.     min_path = min_path[min_time]
     
121. 
     
122.     print('地图大小%d * %d' % (rows,column))
     
123.     print('最佳路径:#%s' % min_path)
     
124.     print('最低耗时:%d' % min_time)
     
125.     print('=' * 60)
     
126. 
     
127. data0 = ["S.....","......","......","......","......",".....E"]
     
128. data1 = ["S...","....","B.WB","..WE"]
     
129. data2 = ["S...","....","B..B","..WE"]
     
130. data3 = ["S.BB.E"]
     
131. data4 = ["S.W...","..WB..","..WW..","....B.","....W.","..B.BE"]
     
132. data5 = ["SBW...",".WWB..","..WW..","......","...WW.","..BWBE"]
     
133. data6 = ["S..BW.",".WWWWW",".W....",".W.W.B",".W.W..","...W.E"]
     
134. data7 = ["EBW.S.",".WWB..","..WW..","......","...WW.","..BWB."]
     
135. data8 = ["S..BW.....",".WWWWWw...",".Wbw......",".W.W.Bw...",".W.W..www.","...W..w...","......w...",".wwww.w..b","..........",".....b..be"]
     
136. data9 = ['s.........','..........','..........','..........','..........','..........','..........','..........','..........','.........e']
     
137. 
     
138. maps(data0)
     
139. maps(data1)
     
140. maps(data2)
     
141. maps(data3)
     
142. maps(data4)
     
143. maps(data5)
     
144. maps(data6)
     
145. maps(data7)
     
146. maps(data8)
     
147. maps(data9)
     

复制代码

测试数据:

1. data0 = ["S.....","......","......","......","......",".....E"]
   
2. data1 = ["S...","....","B.WB","..WE"]
   
3. data2 = ["S...","....","B..B","..WE"]
   
4. data3 = ["S.BB.E"]
   
5. data4 = ["S.W...","..WB..","..WW..","....B.","....W.","..B.BE"]
   
6. data5 = ["SBW...",".WWB..","..WW..","......","...WW.","..BWBE"]
   
7. data6 = ["S..BW.",".WWWWW",".W....",".W.W.B",".W.W..","...W.E"]
   
8. data7 = ["EBW.S.",".WWB..","..WW..","......","...WW.","..BWB."]
   
9. data8 = ["S..BW.....",".WWWWWw...",".Wbw......",".W.W.Bw...",".W.W..www.","...W..w...","......w...",".wwww.w..b","..........",".....b..be"]
   
10. data9 = ['s.........','..........','..........','..........','..........','..........','..........','..........','..........','.........e']

复制代码

雪是梅之香

我怎么有点晕，题目没怎么看懂啊

康小泡

雪是梅之香 发表于 2015-1-23 00:14
我怎么有点晕，题目没怎么看懂啊

你还学python？   

雪是梅之香

kklloo 发表于 2015-1-23 00:28
你还学python？

恩，虽然只是刚开始

挥舞乾坤

题目不太容易理解..晕晕的

hbxtly

又有新题目了啦，支持，学习

挥舞乾坤

@wei_Y 版主大大,为什么第一个例子 结果不是#RRRDDBD

ajian0117

呃，这个参加有难度

wei_Y

挥舞乾坤 发表于 2015-1-23 10:11
@wei_Y 版主大大,为什么第一个例子 结果不是#RRRDDBD

已更新说明。

尧子哥

我怎么有点晕，题目没怎么看懂啊

wei_Y

尧子哥 发表于 2015-1-23 11:57
我怎么有点晕，题目没怎么看懂啊

已更新说明，哪里晕能否说一下，我好改改。。

守护_骑士

看这好难的样子

瞬秒爆加速

困惑，加速状态是持续的，还是有限的？

爱琴海里的星

哇哦~顶起~越来越难啊

挥舞乾坤

瞬秒爆加速 发表于 2015-1-23 16:15
困惑，加速状态是持续的，还是有限的？

应该是持续的,遇到下一个B结束

wei_Y

瞬秒爆加速 发表于 2015-1-23 16:15
困惑，加速状态是持续的，还是有限的？

不持续没有意义吧，走一步就消失时间1+1，直接走是2。。

Mvink

先看看再说

瞬秒爆加速

wei_Y 发表于 2015-1-23 16:36
不持续没有意义吧，走一步就消失时间1+1，直接走是2。。

那栗子一的走法，是怎么回事，都进过B了，为什么没有加速状态？

wei_Y

瞬秒爆加速 发表于 2015-1-23 16:55
那栗子一的走法，是怎么回事，都进过B了，为什么没有加速状态？

一看你打游戏就不多，经过和进入是两回事。。

小龙_h

好难好难好难好难啊！
木有看懂。。。