网站怎么做解析/seo网站排名推广
原题连接：2251 -- Dungeon Master
参考资料：POJ 2251 - Dungeon Master | 眈眈探求
问题：从起点S，经上下左右前后行走，到达目的地E点，返回所经过的路径。(详见原题链接)
输入：
第一行是：层数L，每一层的行数R和列数L，由此构成了一个3D空间；
接下来的L*R行，输入的是相应的Dungeon布局，由#(阻塞)和.(通行)，以及起点S和终点E组成；
例如：
注意：
1 有多组三维地图
2 当输入为“0 0 0”时，结束输入
一 本程序功能及思路
1. 代码设计：用于接收键盘输入，当输入是 0 0 0时，结束输入！
2. 代码设计：将每个三维地图转化为一个数组，建立数组元素的索引值与三维坐标(L;R;C)之间的对应关系；
3 思路：将三维坐标(L;R;C)作为地图中各点(视为顶点)的标签，那么可以根据该标签构建连接图，然后通过BFS(广度优先搜索)的基本思路，完成最短路径查找。
二 Python代码实现
import collections## 将索引转化为(xyz)坐标
def sub2Cor(L, R, C, index):#Z坐标L_new = index // (R * C)# print(L_new)# R坐标index_new = index -L_new*(R*C)R_new = index_new//C# print(R_new)# C坐标C_new = index_new - R_new*C# print(C_new)# 坐标LRC = str(L_new) +";"+ str(R_new)+";"+str(C_new)return LRC# 路径数：
def numOFpath(target,parent):V = target;steps = 0while V!=None:V = parent[V]steps +=1return steps -1def bfs(infor,s,target):# 将起始节点加入到队列中queue = []queue.append(s)# 获得字典的键值，用来查找邻点keys = infor.keys() #这里包含了所有的节点；#如果新生成的节点不在keys中，则说明其不是有效的节点# 设置集合，用来存放已访问过的节点visited = set()visited.add(s)# 设置父节点parent = {s:None}while len(queue) >0:# 弹出节点vertex = queue.pop(0)# 查找邻接点，共6个nodes = []nnl,nnr,nnc = map(int,vertex.split(';'))up = str(nnl+1) + ';' + str(nnr) + ';' +str(nnc)nodes.append(up)down = str(nnl - 1) + ';' + str(nnr) + ';' +str(nnc)nodes.append(down)left = str(nnl) + ';' + str(nnr) + ';' +str(nnc-1)nodes.append(left)right = str(nnl) + ';' + str(nnr) + ';' +str(nnc + 1)nodes.append(right)front = str(nnl) + ';' + str(nnr+1) + ';' +str(nnc)nodes.append(front)behind = str(nnl) + ';' + str(nnr + 1) + ';' +str(nnc)nodes.append(behind)for i in nodes:if i not in visited:if i in keys: #如果节点不在keys中，则说明其不是有效的节点if infor[i][1] != '#':# 说明该节点有效# 添加到队列中queue.append(i)# 添加到已访问中visited.add(i)# 设置父节点parent[i] = vertexif i == target:return numOFpath(target,parent)return -1## 迎接输入数据
data = []
data_size = []
while True:L,R,C = map(int,input().strip().split(' '))if L==0 and R==0 and C==0:breakelse:data_size.append(str(L)+";"+str(R)+";"+str(C))temp = []for i in range(L*R+L-1):if (i+1)%(R+1) ==0: # 处理空行输入input()else:temp1 = input().strip()for i in range(C):temp.append(temp1[i])input() # 处理空行输入data.append(temp)
print(data)
print(data_size)# 格式转换，并用字典存储坐标标签和索引值for i in range(len(data)):sub = data[i] # 读取第一组数据nL,nR,nC = map(int,data_size[i].split(';')) # 读取数据尺寸# 创建一个空字典infor = collections.defaultdict(list)# 存储到字典中for j in range(nL*nR*nC):if sub[j] == 'S': #起始节点s = sub2Cor(nL,nR,nC,j);if sub[j] == 'E': #目标节点target = sub2Cor(nL, nR, nC, j);label = sub2Cor(nL,nR,nC,j);infor[label] = [j,sub[j]]# print(infor)# print(s)# print(target)# 接下来，进行bfs搜索ans = bfs(infor,s,target)if ans != -1:print("Escaped in "+ str(ans) + " minute(s).")else:print("Trapped!")实验测试：
输入：
3 4 5
S....
.###.
.##..
###.######
#####
##.##
##...#####
#####
#.###
####E1 3 3
S##
#E#
###0 0 0输出：
