|
发表于 2017-5-25 00:35:47
|
显示全部楼层
本帖最后由 戴宇轩 于 2017-5-25 00:41 编辑
@wei_Y 最近学算法,看到广度优先搜索,猛然想到这个题目
对于迷宫最短路径来说,广度优先再合适不过了,广度优先不像深度那样找到所有路径,而是从起点一层层地向终点推进,效率惊人...
- from queue import Queue
- # 定义四个方向
- di = (1, 0, -1, 0)
- dj = (0, 1, 0, -1)
- name = 'DRUL'
- '用广度优先搜索算法找两点间最短路径'
- # 返回值: 完整的路径, 例如: 'RULDDRD'
- # 起点坐标: (sx, sy)
- # 终点坐标: (ex, ey)
- def minimum(sx, sy, ex, ey):
- passed = [[0] * M for i in range(N)]
- passed[sx][sy] = ''
- que = Queue()
- que.put((sx, sy))
- x, y = -1, -1
- while x != ex or y != ey:
- x, y = que.get()
- for i, j, n in zip(di, dj, name):
- nx, ny = x + i, y + j
- if 0 <= nx < N and 0 <= ny < M and passed[nx][ny] == 0 and maze[nx][ny] != 'W':
- passed[nx][ny] = '%s%s' % (passed[x][y], n)
- que.put((nx, ny))
- return passed[ex][ey]
- # maze: 迷宫
- # N: 迷宫高度
- # M: 迷宫宽度
- # ups: 加速器位置(列表)
- # path: 最短路径
- # length: 最短路径长度
- def maps(data):
- # 初始化迷宫, 设置高和宽
- global maze, N, M
- maze = [list(i) for i in data]
- N = len(maze)
- M = len(maze[0])
- ups = []
- for x in range(N):
- for y in range(M):
- if maze[x][y] == 'B':
- ups.append((x, y))
- elif maze[x][y] == 'S':
- sx, sy = x, y
- elif maze[x][y] == 'E':
- ex, ey = x, y
- # 先走一遍不经过加速器的路线
- path = minimum(sx, sy, ex, ey)
- length = len(path) * 2
- # 对任意两个加速器, 判断 "先从起点走到第一个加速器, 加速, 从第一个加速器走到第二个加速器, 停止加速, 从第二个加速器走到终点" 的路径是否比原先的路径短. 如果是, 那么替换原先的路径长度和路径
- for i in ups:
- for j in ups:
- a = minimum(sx, sy, *i)
- b = minimum(*i, *j)
- c = minimum(*j, ex, ey)
- new_l = (len(a) + len(c) + 1) * 2 + len(b)
- if new_l < length:
- length = new_l
- path = '%sB%sB%s' % (a, b, c)
- return (path, length)
- #####################################
- 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']
- for i in range(10):
- data = eval('data%d' % (i,))
- print('地图:\n %s\n\n最短路径: %s\n路径长度: %d\n%s' % ('\n '.join(data), *maps(data), '=' * 36))
复制代码 |
|