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;
}
}
}