[백준 6593] 상범 빌딩

from queue import PriorityQueue
import sys

def Dijkstra(G,sp):
    
    INF=float("inf")
    dist=[INF]
    prev=[0]
    Q=set()
    que=PriorityQueue()

    for i in range(1,len(G)):
        if i==sp:
            dist.append(0)
        else:
            dist.append(INF)
        prev.append(0)
        Q.add(i)
        que.put((dist[i],i))

    while Q!=set():
        while True:
            temp_u=que.get()[1]
            if temp_u in Q:
                u=temp_u
                break
        Q.remove(u)
        for i in range(1,len(G[u])+1):
            alt=dist[u]+G[u][i-1][1]
            if alt<dist[G[u][i-1][0]]:
                dist[G[u][i-1][0]]=alt
                prev[G[u][i-1][0]]=u
                que.put((alt,G[u][i-1][0]))
    
    return dist,prev

l,m,n=map(int, sys.stdin.readline().rstrip().split())

while (l,m,n)!=(0,0,0):
    v=l*m*n
    G=[[] for _ in range(v+1)]
    M=[0]*l
    MP=[0]*l

    for i in range(l):
        M[i]=[sys.stdin.readline().rstrip() for _ in range(m)]
        MP[i]=[" " for _ in range(m)]
        sys.stdin.readline()

    INF=float("inf")
    for i in range(l):
        for j in range(m):
            a=[]
            for k in range(n):
            #print(i,j,k,M[i][j])
                if M[i][j][k]=='.':
                    a.append(1)
                if M[i][j][k]=='#':
                    a.append(INF)
                if M[i][j][k]=='S':
                    a.append(1)
                    sp=(i+1,j+1,k+1)
                if M[i][j][k]=='E':
                    a.append(1)
                    ep=(i+1,j+1,k+1)
            MP[i][j]=a

    G=[[] for _ in range(v+1)]

    for i in range(l):
        for j in range(m):
            for k in range(n):
                if k+1<=n-1:
                    G[i*m*n+j*n+k+1].append((i*m*n+j*n+k+1+1,MP[i][j][k+1]))
                if k-1>=0:
                    G[i*m*n+j*n+k+1].append((i*m*n+j*n+k+1-1,MP[i][j][k-1]))
                if j+1<=m-1:
                    G[i*m*n+j*n+k+1].append((i*m*n+j*n+k+1+n,MP[i][j+1][k]))
                if j-1>=0:
                    G[i*m*n+j*n+k+1].append((i*m*n+j*n+k+1-n,MP[i][j-1][k]))
                if i+1<=l-1:
                    G[i*m*n+j*n+k+1].append((i*m*n+j*n+k+1+m*n,MP[i+1][j][k]))
                if i-1>=0:
                    G[i*m*n+j*n+k+1].append((i*m*n+j*n+k+1-m*n,MP[i-1][j][k]))

    sp=(sp[0]-1)*m*n+(sp[1]-1)*n+(sp[2]-1)+1
    ep=(ep[0]-1)*m*n+(ep[1]-1)*n+(ep[2]-1)+1

    ans=Dijkstra(G,sp)[0][ep]
    if ans        print("Escaped in %d minute(s)." % (ans))
    else :
        print("Trapped!")
    
    l,m,n=map(int, sys.stdin.readline().rstrip().split())