|
|
发表于 2015-1-31 15:20:19
|
显示全部楼层
本帖最后由 挥舞乾坤 于 2015-1-31 16:51 编辑
完整版,测试了所有版主提供的路径,并可以实现10*10,支持随机起点和终点,再大的就没有测试了,欢迎测试,鉴于之前版本因为寻路全部由递归完成(递归遍历所有路径真是个大工程)耗时太久,所以又出了这个版本!
- import copy
- #找到指定地图中,两点之间的最短路径
- def maze(data, p1, p2):
- 'data:迷宫数据,p1:起点,p2终点'
-
- rows = len(data) # 地图行数
- column = len(data[0]) #地图列数
- result = [] # 可达路径列表
- x, y = p1
- # fx可移动的方向
- fx = [[0, 1, 'R'], [1, 0, 'D'], [0, -1, 'L'], [-1, 0, 'U']]
- #递归找到最短路径,添加到result列表中
- def move(path, x, y, maps):
- 'path:存放方向字串,x,y:行,列坐标,maps:迷宫地图'
- maps[x][y] = 'W' #记录走过的点,防止重复
- if (x, y) == p2:
- result.append(path) #如果当前坐标等于终点坐标,把路径添加到列表
- #在方向列表中逐个尝试移动
- for i in fx[:]:
- if not (0 <= x + i[0] < rows) or not (0 <= y + i[1] < column):
- continue
- if maps[x + i[0]][y + i[1]] in '.SBE':
- move('%s%s' % (path,i[2]), x + i[0], y + i[1], maps)
- fx_ = re_move(fx) #fx_是一个存放所有方向排列组合的生成器,一共24种组合
- #根据不同的方向排列组合循环调用move,每调用一次添加一个可达路径
- for each in fx_:
- fx = each
- move('', x, y, copy.deepcopy(data))
- #返回最短的路径
- result = {len(x):x for x in result}
- return result[min(result)]
- #生成方向的排列组合,返回一个生成器
- def re_move(fx):
- for pos1 in fx:
- for pos2 in fx:
- if pos2 == pos1:continue
- for pos3 in fx:
- if pos3 in(pos1,pos2):continue
- for pos4 in fx:
- if pos4 in(pos1,pos2,pos3):continue
- yield([pos1,pos2,pos3,pos4])
- #找到指定字符在地图中的位置,返回一个坐标列表
- def find_items(data,item):
- 'data:地图数据,item:要找的字符'
- result = []
- for x,each_row in enumerate(data):
- for y,each_str in enumerate(each_row):
- if each_str == item:
- result.append((x,y))
- return result
- #找到包含加速的路径,返回一个路径列表
- def spend_path(data, s, e, blist):
- 'data:地图数据,s:起点,e:终点,blist:所有加速点的列表'
- result = []
- #循环组合出所有加速路径
- for each in blist:
- for other in blist:
- if each == other:continue
- path = ''
- part1 = maze(data, s, each)
- part2 = maze(data, each, other)
- part3 = maze(data, other, e)
- path = '%s%s%s%s%s' % (part1, 'B', part2, 'B', part3)
- result.append(path)
- return result
- #计算最短路径,返回一个最短的耗时,和最短路径的字典
- def calc_time(path_list):
- 'path_list:路径列表'
- result = {}
- spend = False
- for each_path in path_list:
- count = 0
- for each_char in each_path:
- if each_char == 'B':
- spend = not spend
- count += 1
- continue
- sep = 1 if spend else 2
- count += sep
- result.update({count:each_path})
- return min(result),result
-
-
-
- #主函数了
- def maps(data):
- data = [list(e.upper()) for e in data]
- rows = len(data)
- column = len(data[0])
- for each in data:
- print(each)
- path_list = []
- S = find_items(data,'S')[0] #找起点
- E = find_items(data,'E')[0] #找终点
- B_list = find_items(data,'B') #找所有加速点
- #加速点大余1个,path_list 获得所有加速路径
- if len(B_list) > 1:
- path_list = spend_path(data, S, E, B_list)
- #加入起点到终点,不走加速的路径
- path_list.append(maze(data, S, E))
- #计算所有路径耗时,min_time最小耗时,min_path最短路径
- min_time,min_path = calc_time(path_list)
- min_path = min_path[min_time]
- print('地图大小%d * %d' % (rows,column))
- print('最佳路径:#%s' % min_path)
- print('最低耗时:%d' % min_time)
- print('=' * 60)
- data0 = ["S.....","......","......","......","......",".....E"]
- data1 = ["S...","....","B.WB","..WE"]
- data2 = ["S...","....","B..B","..WE"]
- data3 = ["S.BB.E"]
- data4 = ["S.W...","..WB..","..WW..","....B.","....W.","..B.BE"]
- data5 = ["SBW...",".WWB..","..WW..","......","...WW.","..BWBE"]
- data6 = ["S..BW.",".WWWWW",".W....",".W.W.B",".W.W..","...W.E"]
- data7 = ["EBW.S.",".WWB..","..WW..","......","...WW.","..BWB."]
- data8 = ["S..BW.....",".WWWWWw...",".Wbw......",".W.W.Bw...",".W.W..www.","...W..w...","......w...",".wwww.w..b","..........",".....b..be"]
- data9 = ['s.........','..........','..........','..........','..........','..........','..........','..........','..........','.........e']
- maps(data0)
- maps(data1)
- maps(data2)
- maps(data3)
- maps(data4)
- maps(data5)
- maps(data6)
- maps(data7)
- maps(data8)
- maps(data9)
测试数据:
- data0 = ["S.....","......","......","......","......",".....E"]
- data1 = ["S...","....","B.WB","..WE"]
- data2 = ["S...","....","B..B","..WE"]
- data3 = ["S.BB.E"]
- data4 = ["S.W...","..WB..","..WW..","....B.","....W.","..B.BE"]
- data5 = ["SBW...",".WWB..","..WW..","......","...WW.","..BWBE"]
- data6 = ["S..BW.",".WWWWW",".W....",".W.W.B",".W.W..","...W.E"]
- data7 = ["EBW.S.",".WWB..","..WW..","......","...WW.","..BWB."]
- data8 = ["S..BW.....",".WWWWWw...",".Wbw......",".W.W.Bw...",".W.W..www.","...W..w...","......w...",".wwww.w..b","..........",".....b..be"]
- data9 = ['s.........','..........','..........','..........','..........','..........','..........','..........','..........','.........e']
|
|
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2015-1-30 20:12:55
显身卡
楼主