/*
* Author: Son Pham
* Date: March 13, 2013
* Purpose: Tries to solve this problem using flood fill. I probably didn't
* implement flood fill correctly though.
* Problem: 532 Dungeon Master
* Comments: It took so many tries to get this right...The first mistake was
* the assumption that only 30 moves were needed to escape the dungeon.
* Then it was time limit exceeded...over and over again... I was too
* lazy to dig out my books and notes to find a more efficient
* algorithm. Then I realized that my implementation of flood fill
* was flawed, so I reworked it with the booleans and now it's good.
* I'm pretty certain it could have been implemented better, but this
* was my first attempt at implementing a flood fill. I don't know if
* I did it right though. But at least my solution finally got accepted!
*/
import java.io.*;
public class DungeonMaster {
private static int l;
private static int r;
private static int c;
public static void main(String[] args) {
try{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
while(true){
String read = reader.readLine();
String[] dungeonSize = read.split("\\s+");
l= Integer.parseInt(dungeonSize[0]);
if(l == 0)
return;
r = Integer.parseInt(dungeonSize[1]);
c = Integer.parseInt(dungeonSize[2]);
int[][][] dungeon = new int[l]
[r]
[c];
int starti = 0;
int startj = 0;
int startk = 0;
int endi = 0;
int endj= 0;
int endk = 0;
//Read in dungeon
for(int i = 0; i < l; i++){
for(int j = 0; j < r; j++){
read = reader.readLine();
//System.out.println(read);
int index = 0;
for(int k = 0; k < c; k++){
if(read.charAt(index) == '.')
dungeon[i][j][k] = Integer.MAX_VALUE;
else if(read.charAt(index) == '#')
dungeon[i][j][k] = -1;
else if(read.charAt(index) == 'S'){
dungeon[i][j][k] = 0;
starti = i;
startj = j;
startk = k;
}
else if(read.charAt(index) == 'E'){
dungeon[i][j][k] = Integer.MAX_VALUE;
endi = i;
endj = j;
endk = k;
}
index++;
}
}
read = reader.readLine();
//System.out.println();
}
//Dungeon read in
//System.out.println(starti+" "+startj+" "+startk);
processPath(dungeon,starti, startj, startk);
//System.out.println(dungeon[endi][endj][endk]);
if(dungeon[endi][endj][endk] < Integer.MAX_VALUE)
System.out.println("Escaped in "+dungeon[endi][endj][endk]+" minute(s).");
else
System.out.println("Trapped!");
}
}catch(Exception ex){}
}
public static void processPath(int[][][] d, int si, int sj, int sk){
boolean siup = false;
boolean sidn = false;
boolean sjup = false;
boolean sjdn = false;
boolean skup = false;
boolean skdn = false;
if((si-1 >= 0) && (d[si-1][sj][sk] > (d[si][sj][sk]+1))){
d[si-1][sj][sk] = (d[si][sj][sk]+1);
sidn = true;
//System.out.println("d[si-1][sj][sk] = "+(d[si][sj][sk]+1));
}
if((si+1 < l) && (d[si+1][sj][sk] > (d[si][sj][sk]+1))){
d[si+1][sj][sk] = (d[si][sj][sk]+1);
siup = true;
//System.out.println("d[si+1][sj][sk] = "+(d[si][sj][sk]+1));
}
if((sj-1 >= 0) && (d[si][sj-1][sk] > (d[si][sj][sk]+1))){
d[si][sj-1][sk] = (d[si][sj][sk]+1);
sjdn = true;
//System.out.println("d[si][sj-1][sk] = "+(d[si][sj][sk]+1));
}
if((sj+1 < r) && (d[si][sj+1][sk] > (d[si][sj][sk]+1))){
d[si][sj+1][sk] = (d[si][sj][sk]+1);
sjup = true;
//System.out.println("d[si][sj+1][sk] = "+(d[si][sj][sk]+1));
}
if((sk-1 >= 0) && (d[si][sj][sk-1] > (d[si][sj][sk]+1))){
d[si][sj][sk-1] = (d[si][sj][sk]+1);
skdn = true;
//System.out.println("d[si][sj][sk-1] = "+(d[si][sj][sk]+1));
}
if((sk+1 < c) && (d[si][sj][sk+1] > (d[si][sj][sk]+1))){
d[si][sj][sk+1] = (d[si][sj][sk]+1);
skup = true;
//System.out.println("d[si][sj][sk+1] = "+(d[si][sj][sk]+1));
}
if(sidn)
processPath(d, si-1, sj, sk);
if(siup)
processPath(d, si+1, sj, sk);
if(sjdn)
processPath(d,si,sj-1,sk);
if(sjup)
processPath(d,si,sj+1,sk);
if(skdn)
processPath(d,si,sj,sk-1);
if(skup)
processPath(d,si,sj,sk+1);
}
}
The statements and opinions included in these pages are those of only. Any statements and
opinions included in these pages are not those of Louisiana
State University or the LSU Board of Supervisors.
© 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015