Czech ACM Student Chapter
Czech Technical University in Prague
Charles University in Prague
Technical University of Ostrava
Slovak University of Technology
CTU Open Contest 2007
theseus.c, theseus.C, theseus.p, theseus.java
For one of their clients, ACM prepares a TV advertisement that features ancient heroes, for
example Prometheus, Achilles, Odysseus and many others. To demonstrate how di.cult was
life for these heroes, ACM runs computer simulations of their most famous tasks. In this problem,
we will try to solve the problem of Theseus.
Theseus was an Athenian hero who killed Minotaur, the half-man, half-bull monster residing in
an inescapable Labyrinth constructed by Daedalus. The hardest part of Theseus` task was not
killing the monster - the legend says Minotaur was just sleeping when Theseus came to him.
Thus, the hero was able to batter the monster with his bare hands. But then the real challenge
came: to find the way out. As you may know, Ariadne, beautiful daughter of king Minos, played
an important role in this part. But that`s a di.erent story.
As the technology advanced a lot since the ancient times, there are several important di.erences
in today`s simulations:
1. Labyrinth-making skills advanced as well. Two-dimensional labyrinths are not a big challenge
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
moves in steps, each step means travelling between two neighboring empty hypercubes in any
dimension. Two hypercubes are considered neighboring, if and only if the di.erence in their
space coordinates is exactly one in one dimension, and zero in all other dimensions.
2. Our Minotaur is stronger, thus, it is no more possible to batter him with bare hands. Theseus
must use a sword which lies somewhere inside the labyrinth. Note that before he takes the sword,
he cannot go through the hypercube where Minotaur resides!
The input consists of several labyrinth descriptions. Each description begins with a line contain-
ing a single integer number d (2 . d . 20) - the number of dimensions. On the second line of
each description, there are d integer numbers n
, ..., n
separated by spaces. These numbers
give the size of the labyrinth in every dimension, measured in unit hypercubes (.i :2. n
may assume that the total number of hypercubes in any labyrinth will not exceed 2
Then a labyrinth map follows, the description is defined recursively: Two-dimensional labyrinth
(of the size n
) is described by n
lines containing n
characters each. Every character
describes a single hypercube ("square" in the case of 2 dimensions) and is either "#"(rock),"."
(free space), or one of uppercase letters "T" (Theseus` position), "M" (Minotaur), and `S` (sword).
Each of these three objects will appear exactly once in the whole labyrinth. The hypercubes
containing the letters are considered "empty" otherwise, i.e., Theseus can walk (and must walk)
For better clarity of the input, each two-dimensional map is followed by one empty line.