1. 

package graphs.pathfinding.dungeonMaster;

/**
 * FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS10/11
 * Problem: 532 Dungeon Master
 * Link: http://uva.onlinejudge.org/external/5/532.html
 *
 * @author Patrick Bédat
 * @version 1.0, 11/10/2010
 *
 * Method : Dijkstra
 * Status : Accepted
 * Runtime: 1.168
 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main
{

	private static List<DungeonNode> nodeList;

	public static void main(String... args) throws IOException
	{
		int nLevels = -1;
		int height;
		int width;

		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

		do
		{
			StringTokenizer st = new StringTokenizer(reader.readLine());
			nLevels = Integer.parseInt(st.nextToken());
			height = Integer.parseInt(st.nextToken());
			width = Integer.parseInt(st.nextToken());

			if (nLevels == 0)
				return;

			nodeList = new ArrayList<DungeonNode>();

			char[][][] dungeon = new char[nLevels][height][width];

			for (int l = 0; l < nLevels; l++)
			{
				for (int y = 0; y < height; y++)
				{
					String line = reader.readLine();
					while (l == 0 && line.isEmpty())
						line = reader.readLine();
					dungeon[l][y] = line.toCharArray();
				}
				reader.readLine();
			}

			DungeonNode start = null;
			DungeonNode end = null;

			for (int l = 0; l < nLevels; l++)
			{
				char[][] level = dungeon[l];
				char[][] nextLevel = null;
				if (l + 1 < nLevels)
					nextLevel = dungeon[l + 1];

				for (int y = 0; y < height; y++)
				{
					char[] line = level[y];
					char[] nextLine = null;
					if (y + 1 < height)
						nextLine = level[y + 1];

					for (int x = 0; x < width; x++)
					{
						if (line[x] == '#')
							continue;

						DungeonNode currentNode = new DungeonNode(l, x, y);

						currentNode = GetOrAddNode(currentNode);

						if (line[x] == 'S')
							start = currentNode;
						if (line[x] == 'E')
							end = currentNode;

						if (x + 1 < width && line[x + 1] != '#')
						{
							DungeonNode rightNeighbour = new DungeonNode(l, x + 1, y);

							rightNeighbour = GetOrAddNode(rightNeighbour);

							rightNeighbour.neighbours.add(currentNode);
							currentNode.neighbours.add(rightNeighbour);
						}

						if (y + 1 < height && nextLine[x] != '#')
						{
							DungeonNode bottomNeighbour = new DungeonNode(l, x, y + 1);

							bottomNeighbour = GetOrAddNode(bottomNeighbour);
							
							bottomNeighbour.neighbours.add(currentNode);
							currentNode.neighbours.add(bottomNeighbour);
						}
						if (l + 1 < nLevels && nextLevel[y][x] != '#')
						{
							DungeonNode nextLevelNeighbour = new DungeonNode(l + 1, x, y);

							nextLevelNeighbour = GetOrAddNode(nextLevelNeighbour);

							nextLevelNeighbour.neighbours.add(currentNode);
							currentNode.neighbours.add(nextLevelNeighbour);
						}
					}
				}
			}

			HashMap<DungeonNode, Integer> distances = new HashMap<DungeonNode, Integer>();
			PriorityQueue<DungeonNode> stack = new PriorityQueue<DungeonNode>(30, new NodeDistanceComparator(distances));
			stack.add(start);
			distances.put(start, 0);
			HashMap<DungeonNode, DungeonNode> predecessors = new HashMap<DungeonNode, DungeonNode>();
			predecessors.put(start, null);

			while (!stack.isEmpty())
			{
				DungeonNode currentNode = stack.poll();

				if (currentNode.equals(end))
					break;

				for (DungeonNode neighbour : currentNode.neighbours)
				{
					Integer neighbourDistance = distances.get(neighbour);
					if (neighbourDistance == null)
						neighbourDistance = Integer.MAX_VALUE;
					Integer currentDistance = distances.get(currentNode);

					if (currentDistance + 1 < neighbourDistance)
					{
						distances.put(neighbour, currentDistance + 1);
						stack.add(neighbour);
						predecessors.put(neighbour, currentNode);
					}
				}
			}

			int pathSize = 0;

			DungeonNode current = end;

			while (current != start && predecessors.containsKey(current))
			{
				current = predecessors.get(current);
				pathSize++;
			}

			if (pathSize == 0)
				System.out.println("Trapped!");
			else
				System.out.println("Escaped in " + pathSize + " minute(s).");

		}
		while (true);
	}

	private static DungeonNode GetOrAddNode(DungeonNode node)
	{
		int i = Collections.binarySearch(nodeList, node);

		if (i >= 0)
			node = nodeList.get(i);
		else
		{
			i = Math.abs(i + 1);
			nodeList.add(i, node);
		}
		return node;
	}

	private static class DungeonNode implements Comparable<DungeonNode>
	{

		public int level;
		public int x;
		public int y;
		public LinkedList<DungeonNode> neighbours = new LinkedList<DungeonNode>();

		public DungeonNode(int l, int x, int y)
		{
			this.level = l;
			this.x = x;
			this.y = y;
		}

		@Override
		public String toString()
		{
			return String.format("[l:%d, x:%d, y:%d]", level, x, y);
		}

		@Override
		public int hashCode()
		{
			return level + x * 100 + y * 10000;
		}

		@Override
		public boolean equals(Object obj)
		{
			final DungeonNode other = (DungeonNode) obj;

			return this.hashCode() == other.hashCode();
		}

		public int compareTo(DungeonNode o)
		{
			if (this.hashCode() < o.hashCode())
				return -1;
			else if (this.hashCode() > o.hashCode())
				return 1;
			return 0;
		}
	}

	private static class NodeDistanceComparator implements Comparator<DungeonNode>
	{

		HashMap<DungeonNode, Integer> distance;

		public NodeDistanceComparator(HashMap<DungeonNode, Integer> distances)
		{
			distance = distances;
		}

		public int compare(DungeonNode o1, DungeonNode o2)
		{
			if (o1 == null || distance.get(o1) > distance.get(o2))
				return 1;
			if (o2 == null || distance.get(o1) < distance.get(o2))
				return -1;
			return 0;
		}
	}
}