三维BFS

python标准库collections中的类deque比list有更低的时间和空间复杂度

python3代码

from collections import deque


def bfs(z, x, y):
    dist[z][x][y] = 0
    queue = deque()
    queue.append((z, x, y))
    while len(queue):
        z, x, y = queue.popleft()

        for i in range(6):
            xx, yy, zz = x + dx[i], y + dy[i], z + dz[i]
            if 0 <= zz < l and 0 <= xx < r and 0 <= yy < c \  # 判断边界条件
                    and q[zz][xx][yy] != '#' and dist[zz][xx][yy] == -1:  # 是否走过
                dist[zz][xx][yy] = dist[z][x][y] + 1
                if q[zz][xx][yy] == 'E':
                    return dist[zz][xx][yy]
                queue.append((zz, xx, yy))
    return -1


dz = [-1, 1, 0, 0, 0, 0]
dx = [0, 0, -1, 1, 0, 0]
dy = [0, 0, 0, 0, -1, 1]
while True:
    l, r, c = map(int, input().split())
    if l == 0:
        break

    dist = [[[-1] * c for _ in range(r)] for _ in range(l)]
    start_x, start_y, start_z = 0, 0, 0
    q = []
    for i in range(l):
        q_tmp = []
        for j in range(r):
            ipt = input()
            for index, item in enumerate(ipt):
                if item == 'S':
                    start_z, start_x, start_y = i, j, index
            q_tmp.append(list(ipt))
        to_next = input()
        q.append(q_tmp)

    distance = bfs(start_z, start_x, start_y)

    if distance == -1:
        print("Trapped!")
    else:
        print("Escaped in %d minute(s)." % distance)