Ada has found an old video game called multistory labyrinth. As its name indicates, the game consists in a labyrinth (a field with multiple roads and walls where you should find a route from an origin point to a destination point) with a little difference: This labyrinth is conformed for several floors (like a building) where each floor belongs to the same labyrinth and you have elevators that connects different floors. The source point and the destination point could be in any floor. Each movement made by Ada in x, y or z (moving to north, sur, east, west, up or down a floor) counts like a step. Ada is a strategic women and she doesn’t want spend more steps than the necessary to resolve the labyrinth. Can you make a program that compute the minimum number of steps required to reach the end of the labyrinth? The labyrinth is represented like a set of floors, and every floor is described as a grid with the next conventions: • “#” Represents a wall. • “.” Represents a free square. • “-” Represents an elevator (Can go up or down to the next floor if and only if the next floor have an elevator in the same point). Elevators could be used as a free squares too, meaning that Ada could pass through them without changing floor. • “S” Starting point. Could be in any floor. • “E” End point. Could be in any floor. Example of one text case representing the first, second and third floor. The black squares denote walls, the white free squares and those marked with an “-” are elevators. Solution to the above proble. Each circle denotes an step. Note how from the first floor go to the third and then down again to the first, reaching the end point in 13 steps.
2/2 Input Input consist of multiple test cases. Each case starts with 3 integers l, w and h denoting respectively the number of rows and columns of each floor of the labyrinth, followed by the number of floors (1 ≤ w,l,h ≤ 100). After that will be the description of each one of the h floors (Starting from the floor 1 and ending with the floor h). Each floor is conformed for w lines of l characters denoting the floor with the conventions given in the exercise. It is guaranteed that there will be one and only one character ‘E’ and one and only one character ‘S’ in the description of the building for each test case. There is a blank space after the description of each floor. Input ends when l = 0, w = 0, h = 0. Output For each test case print a single line: the minimum number of steps needed to reach the end of the labyrinth (or ‘-1’ if it’s not possible to find a way). Sample Input 443 S..- #.## ..#- -#E. ...- .### .#.- -#.. .#.- .#.# .#.- ...# 242 .-.. .... S--E #### 000 Sample Output 13 3