No One's Labyrinth
By Leandro Zatesko, UFFS 
Brazil
By Leandro Zatesko, UFFS Brazil
Never take one of the faces from the House of Black and White if you are not ‘No One’, even if it's to kill Meryn Trant, otherwise you shall be blind, besides receiving many other punishments. Perhaps you see yourself becoming ‘No One’. Perhaps that is what is happening to Arya. Or not. The fact is that now she is blind and has been put in a labyrinth full of locked doors. Can you help her?
The locks of the doors present in the labyrinth where Arya is are of 7 types: A, B, C, D, E, F and G. There are also some copies of keys around the labyrinth, which can be of types a, b, c, d, e, f or g. A key of type a opens a door of type A, a key of type b opens a door of type B etc. Once Arya has opened a door with a key, the door remains opened, of course, and Arya can take the key with her to open as many doors as she wants of that type. In the labyrinth there is exactly one exit: a hole in the floor through which Arya can enter the tunnel that will lead her safely to the exit of the House of Black and White.
The input represents the labyrinth and consists of at most 100 lines with at most 100 characters different from end-of-line each, and the number of characters per line is always the same. The character @ identifies the position where Arya is, the character * identifies the exit, the walls of the labyrinth are identified by the character #, the doors by characters in the set {A, …, G}, the keys by characters in the set {a, …, g}, and the other free positions by the character . (dot). The total of characters in the labyrinth different from # and from . is at most 100, and there is exactly one character * and one character @. Arya always spends 1 second to move from one position to another, and she moves only in horizontal or vertical directions, for she is afraid of hitting her little toe against a corner of a wall, since the walls are square-shaped. The input ends in end-of-file.
Print a line containing a single integer, which is meant to represent the minimum time, in seconds, that Arya needs in order to leave the labyrinth. If it is not possible for Arya to leave the labyrinth, print a line containing only two characters - (hyphen), representing the closed eyes with which Arya shall need to live until she is Arya no more.
| Input Samples | Output Samples |
|
.............. |
35 |
|
-- |