|
|
发表于 2015-1-29 15:28:05
|
显示全部楼层
本帖最后由 戴宇轩 于 2015-1-31 13:56 编辑
成品 12
版本: Python 3.4.0a0- import re #分开路径用
- import sys #报错用
- class Go_to_B: #向加速器移动的类
- def __init__(self, direction, opposite): #要传入四个方向和相反路径字典
- self.result = [] #结果存放处
- self.direction = direction #方向存放处
- self.opposite = opposite #相反路径字典
- def __call__(self, path, field, history): #被调用时
- (x, y) = history[-1] #找到现在位置
- if field[x][y] == 'B': #如果找到了加速器
- self.result.append(path) #结果增加这条路径
- del history[-1];return 0 #推向前一个点, 向其他方向继续寻找
- for i in self.direction: #搜索四个方向
- (x, y) = (history[-1][0] + i[0], history[-1][1] + i[1]) #假定向这个方向移动1格
- if not ((x, y) in history or field[x][y] == 'W'): #如果超出边界 or 走过这个点(非递归造成) or 前面被水挡住了, 就搜索另一个方向
- history+=[(x, y)] #如果前面是通路, 将这个点加入history, 下次递归就从这个点开始
- self(path + i[2], field, history) #递归
- del history[-1] #如果找到一条死路(再找就回去了), 就回到上一个点, 继续寻找
- def __str__(self): #被str()时
- self.result.sort(key = len) #找到最短的一条路
- temp = self.result and self.result[0] or '' #如果整个迷宫里没有加速器, 开头结尾路径为空
- return temp + (temp and 'B' or '') + ''.join([self.opposite[i] for i in temp[::-1]]) #并返回
- def fix(path): #用来消除路径中的[RL|LR|UD|DU|BB]
- while path.replace('LR', '').replace('RL', '').replace('UD', '').replace('DU', '').replace('BB', '') != path:
- path = path.replace('LR', '').replace('RL', '').replace('UD', '').replace('DU', '').replace('BB', '')
- return path
- def checkroute(data): #主函数
- direction = ((0, 1, 'R'), (1, 0, 'D'), (-1, 0, 'U'), (0, -1, 'L')) #定义四个方向
- data = ['W' * (len(data[0]) + 2)] + ['W' + i + 'W' for i in data] + ['W' * (len(data[-1]) + 2)] #给迷宫加上墙壁
- opposite = {'R': 'L', 'U': 'D', 'D': 'U', 'L': 'R'} #相反路径字典
- (start_path, end_path) = ([], []) #开始和结束到加速器的最短距离
- (S_axis, E_axis) = ([], [])
- ##### 这个函数段用于找到S和E的坐标
- x = 0
- for i in data:
- y = 0
- for j in i:
- if j == 'S':S_axis.append((x, y))
- if j == 'E':E_axis.append((x, y))
- y += 1
- x += 1
- ##### 结束
- ##### 判断起点, 终点个数是否正确
- if len(S_axis) != 1:sys.exit('起点个数不正确!')
- if len(E_axis) != 1:sys.exit('终点个数不正确!')
- ##### 结束
- def view_all_path(data): #这个函数用来找到所有路径(不兜圈)
- result = [] #结果路径存放处
- ########## 这个脚本段用来记录起点和终点到加速器后返回的最短距离
- start_path_temp = Go_to_B(direction, opposite)
- start_path_temp('', data, S_axis[:]) #因为Move_to_B()()会把S_axis删光, 浅拷贝一次
- start_path.append(str(start_path_temp))
- end_path_temp = Go_to_B(direction, opposite)
- end_path_temp('', data, E_axis)
- end_path.append(str(end_path_temp))
- ########## 结束
- def serach(path, field, history): #搜索函数
- (x, y) = history[-1] #找到现在位置
- if field[x][y] == 'E': #如果找到了终点
- result.append(path) #结果增加这条路径
- del history[-1];return 0 #推向前一个点, 向其他方向继续寻找
- for i in direction: #搜索四个方向
- (x, y) = (history[-1][0] + i[0], history[-1][1] + i[1]) #假定向这个方向移动1格
- if not ((x, y) in history or field[x][y] == 'W'): #如果超出边界 or 走过这个点(非递归造成) or 前面被水挡住了, 就搜索另一个方向
- history+=[(x, y)] #如果前面是通路, 将这个点加入history, 下次递归就从这个点开始
- serach(path + i[2] + ('B' if field[x][y] == 'B' else ''), field, history) #递归
- del history[-1] #如果找到一条死路(再找就回去了), 就回到上一个点, 继续寻找
- serach('', data, S_axis) #搜索, 此时路径为空, 传入起点位置
- return result #将找到的所有路径返回
- ###### 寻找路径函数结束
- raw_path = view_all_path(data) #得到只走一次的路径, 传入迷宫
- factored_path = [] #所有(含开头结尾加速器)路径存放处
- start_path = start_path[0] #开头加速器路径
- end_path = end_path[0] #结尾加速器路径
- final_path = [] #最终路径
- least = {} #时间与路径的字典
- for i in raw_path: #一共有四种路径(原路径, 开头加速器 + 原路径, 原路径 + 结尾加速器, 开头加速器 + 原路径 + 结尾加速器)
- factored_path += [i, start_path + i, i + end_path, start_path + i + end_path]
- for i in [fix(i) for i in factored_path]: #逐个查看消除重复路径后的路径
- if i.count('B') in (0, 2): #如果有0个或2个B在路径内
- final_path.append(i) #直接放入正确路径
- elif i.count('B') > 2: #如果有多于两个B, 仅保留最前和最后的B(这样时间少)
- frount = i.index('B') + 1
- back = len(i) - i[::-1].index('B') - 1
- final_path.append(i[:frount] + i[frount:back].replace('B', '') + i[back - 1:])
- final_path.append(i.replace('B', '')) #再加入一个全程不加速的路径(以上判断皆通过此处)
- for i in final_path: #查看所有正确路径
- all_time = 0 #每条路径时间一开始是0
- split_path = re.findall('[URLD]+(?=B)|B[URLD]+B|(?<=B)[URLD]+|[URLD]+', i) #用正则表达式将路径分开, 如下
- #例子: 'RRRRRBUUUBLLL' ------> ['RRRRR', 'BUUUB', 'LLL']
- for j in split_path: #逐个查看所有分开路径
- if j[0] == 'B': #如果处于加速状态
- all_time += len(j) #时间和加上加速后的路径长度(单位: 1)
- else: #否则(非加速状态)
- all_time += len(j) * 2 #时间和加上现在路径的总长度(单位: 2)
- least[all_time] = i #least的现在总时间对应现在的路径
- print('最短时间: %s 路径:' % min(least), least[min(least)]) #输出最短的时间和对应的路径, Done!
- # -*- -*- -*- -*- -*- # 测试数据
- No_1 = ["SBW...",".WWB..","..WW..","......","...WW.","..BWBE"]
- No_2 = ["S..BW.",".WWWWW",".W....",".W.W.B",".W.W..","...W.E"]
- checkroute(No_1)
- checkroute(No_2)
|
评分
-
查看全部评分
|
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
楼主
显身卡
发表于 2015-1-25 17:49:11
时间还早。
我复习完物理就改进, and这个活动开的真不是时候, 我最近要考期末。。。