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

Mvink

支持小甲鱼

freeparty

我来看看

freeparty

我来看看{:1_1:}

煈愛

有点难啊，，，，坐等大神上代码去领悟。

小甲鱼的二师兄

看不懂→_→我们需要写什么内容？

wei_Y

小甲鱼的二师兄 发表于 2015-1-24 20:07
看不懂→_→我们需要写什么内容？

我写上了吧，可以跑出最短时间路径的函数。。

小龙_h

艾玛，终于看懂题目神马意思啦！感觉好难哦！

从0到100

不会也要支持下~

咚咚呆

看看

丸子酱1016

领奖品~~

挥舞乾坤

遇到加速可以选择不进,但是如果行进路线上有3个加速状态或者以上,再加速状态下路过B,是否可以选择退出或不退出加速状态

wei_Y

挥舞乾坤 发表于 2015-1-25 11:36
遇到加速可以选择不进,但是如果行进路线上有3个加速状态或者以上,再加速状态下路过B,是否可以选择退出或不 ...

可以。在B点是选择进出，可以进也可以不进。

挥舞乾坤

基本功能已经写好了,有些乱,整理一下,再发

戴宇轩

本来可以写完了, 考虑到地图可以是66的, 暂时无法应对太多障碍…… 今天应该能写好

shaoguanfa

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

挥舞乾坤

先发出来测试一下,抛砖引玉了,代码效率太低了,5*6要10几秒,6*6,几分钟,先测试一下功能吧,一会出去喝大酒,回来再改
1*6的问题改过了,但效率还是硬伤啊

1. def maze():
   
2.     '之后加上判断输入是否合法的代码'
   
3. 
   
4.     str_map = input('输入一个字符串格式的迷宫地图(SBW.,....,....,..BE):')
   
5. 
   
6.     #处理字符串,返回二维列表形式的地图及元组形式的地图范围
   
7.     limit,data = str_to_list(str_map)
   
8.    
   
9.     #遍历所有可达路径,返回列表
   
10.     list_path = get_path(data,limit)
    
11. 
    
12.     #路径加速减速方面的处理
    
13.     list_path = chuli(list_path)
    
14. 
    
15.     #计算耗时
    
16.     min_time,min_path = calc(list_path)
    
17. 
    
18.     print('地图大小:%d * %d' % limit)
    
19.     print('#',min_path, sep = '')
    
20.     print('最低耗时:%d' % min_time)
    
21.    
    
22. def str_to_list(str_map):
    
23.     '处理字符串,返回一个二维列表形式的地图列表'
    
24.     str_map = str_map.upper()
    
25.     list_map = [ list(x) for x in str_map.split(',')]
    
26.     map_limit = (len(list_map),len(list_map[0]))
    
27.     return map_limit,list_map
    
28. 
    
29. def get_path(data,limit):
    
30.     '便利所有可达路径'
    
31.     result = []
    
32.     fx = [[0, 1, 'R'], [1, 0, 'D'], [0, -1, 'L'], [-1, 0, 'U']]
    
33.     x_limit,y_limit = limit
    
34.    
    
35.     def move(path, maps, path_stack = [(0,0)]):
    
36.         '这里有点问题,由于用的是递归,代码效率太低了,6*6太久,5*6勉强可以,囧'
    
37.         x, y = path_stack[-1]
    
38.         if (x, y) == (x_limit - 1,y_limit - 1):
    
39.             result.append(path)
    
40.             path_stack.pop()
    
41.             return
    
42.         
    
43.         for i in fx:
    
44.             x, y = path_stack[-1]            
    
45.             x, y = x + i[0], y + i[1]
    
46.             if x not in range(x_limit) or y not in range(y_limit) \
    
47.                or (x,y) in path_stack or maps[x][y] == 'W':
    
48.                 x = max(min(x, x_limit - 1), 0)
    
49.                 y = max(min(y, y_limit - 1), 0)
    
50.                 continue                        
    
51.             path_stack.append((x,y))
    
52.             if maps[x][y] == 'B':
    
53.                 move(path + i[2] + 'B', maps)
    
54.             else:
    
55.                 move(path + i[2], maps)            
    
56.         path_stack.pop()
    
57.     move('',data)
    
58.    
    
59.     return result
    
60. 
    
61. def chuli(list_path):
    
62.     new_list = []
    
63.     for each in list_path:
    
64.         if each.count('B') == 1:
    
65.             each = each.replace('B','')
    
66.         if each.count('B') == 2:
    
67.             if each.rindex('B') - each.index('B') < 3:
    
68.                 each = each.replace('B','')
    
69.         elif each.count('B') > 2:
    
70.             first = each.index('B')
    
71.             end = each.rindex('B') - len(each) + 1
    
72.             each = each.replace('B','')
    
73.             each = each[:first] + 'B' + each[first:]
    
74.             each = each[:end] + 'B' + each[end:]
    
75.             
    
76.         new_list.append(each)
    
77.     return new_list
    
78.          
    
79. def calc(list_path):
    
80.     min_sep = 100
    
81.     min_path = ''
    
82.     for each in list_path:
    
83.         count = 0
    
84.         spend = -1
    
85.         for s in each:
    
86.             if s == 'B':
    
87.                 count += 1
    
88.                 spend = -spend
    
89.             elif spend == 1:
    
90.                 count += 1
    
91.             else:
    
92.                 count += 2
    
93.         if count < min_sep:
    
94.             min_sep = count
    
95.             min_path = each
    
96.     return min_sep,min_path
    
97. 
    
98.             
    
99. if __name__ == '__main__':
    
100.     maze()
     

复制代码

戴宇轩

戴宇轩 发表于 2015-1-25 16:51
这是个半成品, 暂时没有考虑加速器B的情况, 而且路径暂时不完整, 还是先发上来看看吧, 下次改

!!!!!我没有设计回路, 看来要换一个思路了

挥舞乾坤

挥舞乾坤 发表于 2015-1-25 16:04
先发出来测试一下,抛砖引玉了,代码效率太低了,5*6要10几秒,6*6,几分钟,先测试一下功能吧,一会出去喝大酒,回 ...

SBW...,.WWB..,..WW..,......,...WW.,..BWBE

地图大小:6 * 6
#DDRDRRRRDD
最低耗时:20

测试了一下这个,不知道结果对不对,障碍多,速度还是挺快的,是不是因为障碍多,路径少了,就快了啊,没障碍,还是很慢