- Input file: theseus.in
- Output file: theseus.out
- Time limit: 2 seconds
- Memory limit: 64 Megabytes
of their clients, ACM prepares a TV advertisement that features ancient heroes,
Prometheus, Achilles, Odysseus and many others. To demonstrate how di.cult
for these heroes, ACM runs computer simulations of their most famous tasks. In
try to solve the problem of Theseus.
was an Athenian hero who killed Minotaur, the half-man, half-bull monster
inescapable Labyrinth constructed by Daedalus. The hardest part of Theseus` task
the monster - the legend says Minotaur was just sleeping when Theseus came to
the hero was able to batter the monster with his bare hands. But then the real
to find the way out. As you may know, Ariadne, beautiful daughter of king Minos,
important role in this part. But that`s a di.erent story.
technology advanced a lot since the ancient times, there are several important
Labyrinth-making skills advanced as well. Two-dimensional labyrinths are not a
anymore. Thus, our labyrinth is d-dimensional. It looks like a regular
"grid" of n
(hyper)cubes, each of them being either empty (corridor) or filled
with a rock (wall). Theseus
in steps, each step means travelling between two neighboring empty hypercubes in
dimension. Two hypercubes are considered neighboring, if and only if
the di.erence in their
coordinates is exactly one in one dimension, and zero in all other
Minotaur is stronger, thus, it is no more possible to batter him with bare
use a sword which lies somewhere inside the labyrinth. Note that before he takes
cannot go through the hypercube where Minotaur resides!
input consists of several labyrinth descriptions. Each description begins with a
single integer number d (2 . d . 20) - the number of dimensions. On the second
description, there are d integer numbers n
separated by spaces. These numbers
the size of the labyrinth in every dimension, measured in unit hypercubes (.i
assume that the total number of hypercubes in any labyrinth will not exceed
labyrinth map follows, the description is defined recursively: Two-dimensional
described by n
characters each. Every character
describes a single hypercube ("square" in the case of 2 dimensions)
and is either "#"(rock),"."
space), or one of uppercase letters "T" (Theseus` position), "M" (Minotaur), and
these three objects will appear exactly once in the whole labyrinth. The
containing the letters are considered "empty" otherwise, i.e., Theseus
can walk (and must walk)
better clarity of the input, each two-dimensional map is followed by one empty
d>2, any d-dimensional labyrinth is a sequence of n
"layers", each layer being a description
(d - 1)-dimensional labyrinth.
last labyrinth description is followed by a line containing zero. This line
and no output should be produced for it.
each labyrinth, output the sentence "Theseus needs S steps.", where S is the
possible amount of steps needed to reach the hypercube with the sword,
the hypercube with
Minotaur, and then back to the original Theseus` position (where the
exit is supposed to be). It
possible to leave the labyrinth area, i.e., all hypercubes outside the labyrinth
Exit may appear in an inner hypercube, it may not reside on the
is not possible to solve the situation at all, output sentences "No solution.
for Sample Input
Theseus needs 8 steps.
solution. Poor Theseus!
Theseus needs 40 steps.