1.

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS11
* @author Beinhofer Christian
* @version 1.0
*
* Flooding-Algorithmus
* 8976857 532 Dungeon Master Accepted C++ 0.036 2011-06-22 14:01:22
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=7&problem=473
*/

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <vector>

int L, C, R;
char map[31][31][31];
unsigned int res[31][31][31];

struct Item {
Item(int l, int r, int c) : l(l), r(r), c(c)
{
}

int l;
int r;
int c;
};

std::vector<Item> items;

unsigned int time = -1;

int next[6][3] = {
{-1, 0, 0}, {1, 0, 0},
{0, -1, 0}, {0, 1, 0},
{0, 0, -1}, {0, 0, 1},
};

void flood(int l, int r, int c)
{
int lev, col, row;

int nextsteps = res[l][r][c] + 1; // Get step count to the next field

for(int i = 0; i < 6; i++)
{
lev = l + next[i][0];
row = r + next[i][1];
col = c + next[i][2];

if(lev < 0 || row < 0 || col < 0 || lev == L || row == R || col == C)
continue;

if(map[lev][row][col] == 'E')
{
if(time > nextsteps) time = nextsteps;
return;
}

if(res[lev][row][col] > nextsteps)
{
res[lev][row][col] = nextsteps;
items.push_back(Item(lev, row, col));
}
else if((map[lev][row][col] == 'S' || map[lev][row][col] == '.') && res[lev][row][col] + 1 < res[l][r][c])
{
// Found shortcut use it and run again
res[l][r][c] = res[lev][row][col] + 1;
items.push_back(Item(l, r, c));
return;
}
}
}

int main()
{
while(scanf("%d %d %d", &L, &R, &C) && (L != 0))
{
time = -1;
// read the whole map
for(int l = 0; l < L; l++)
{
for(int r = 0; r < R; r++)
{
scanf("%s", map[l][r]);
for(int c = 0; c < C; c++)
{
if(map[l][r][c] == '.')
{
res[l][r][c] = -1;
}
else
{
res[l][r][c] = 0;
if(map[l][r][c] == 'S')
{
items.push_back(Item(l, r, c));
}
}
}
}
}

// recusivbe version would get too expensive
while(!items.empty())
{
Item item = items[items.size() - 1];
items.pop_back();
if(res[item.l][item.r][item.c] < time - 1)
flood(item.l, item.r, item.c);
}

if(time == -1)
printf("Trapped!\n");
else
printf("Escaped in %d minute(s).\n", time);
}

return 0;
}

--------------------------------------------------------


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