参考资料：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 = 0
while V!=None:
V = parent[V]
steps +=1
return steps -1
def dfs(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] = vertex
if 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:
break
else:
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 = dfs(infor,s,target)
if ans != -1:
print("Escaped in "+ str(ans) + " minute(s).")
else:
print("Trapped!")
实验测试：
? ? ? ? 输入：
3 4 5
S....
.###.
.##..
###.#
#####
#####
##.##
##...
#####
#####
#.###
####E
1 3 3
S##
#E#
###
0 0 0? ? ? ? 输出：
