|
|
发表于 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-29 15:28:05
楼主
已更新说明。
一看你打游戏就不多，经过和进入是两回事。。