Yet another problem with amazing story by Vladimir V. Zelevinsky - thanks a lot!
Previously, on "The Amazing Adventures of Alabama Adams, the Adjunct Archeologist!" (also known as "AAAAAA!"), our protagonist finally defeated her arch-enemy, the time-traveling ghost zombie of Emperor Nero, retrieving from him the priceless historical relic, the Nose of Chronos.
Now all she needs to do is to return the nose to the statue of Chronos.
Herein lies her first problem.
The statue of Chronos is located at the far end of the terrible labyrinth, the notorious Catacombs of Chronos.
The history behind the Catacombs is lost; even the most learned archeologists do not know why, exactly, the builders of the ages past had constructed an elaborate labyrinth of thousands of chambers and, moreover, went through the trouble of connecting these chambers with hundreds of clockwork-operated doors. Every click (a click being an ancient unit of time), the powerful mechanism of the catacombs opens every closed door and closes every open door.
The map of the Catacombs is well-known (it is your puzzle input). Professor Adams, like every well-educated archeologist, certainly knows it by heart.
Normally, navigating the Catacombs presents no challenge: one can take any path toward the exit. If one runs into a closed door, one merely has to wait for a single click for it to open.
"Aaaaaa!" says Professor Adams, standing at the entrance to the Catacombs. "Ladybugs. Why’d it have to be ladybugs?!"
This is, indeed, her second problem. The Catacombs are crawling with ladybugs. Due to a traumatic childhood incident (involving an incautious ladybug, a flammable party hat, and a candle on her birthday cake), Alabama suffers from an acute case of coccinellidaephobia. If she were to stand still for even one click, she'd be in danger of the ladybugs swarming all over her. This means she has to keep moving.
Every click, Alabama travels the distance of exactly two chars (a char being an ancient unit of distance) in one
of the four cardinal directions, North (N), West (W), South (S), or East (E).
Let's take a look at a small example map (this one is 7 by 7 chars). Here, # means solid rock; | is a
door that is currently closed; . is a door that is currently open.
#######
# . | #
#|#|#|#
# . . #
#|#|#.#
# . | #
#######
Alabama starts out in the chamber in the north-west (upper left) corner of the map (coordinates 1, 1, if the
top left corner is taken to be 0, 0). To the North and to the West is solid rock; the door to the South is
currently closed. This means she must leap to the East, ending up at the coordinates 3, 1. As soon as she
lands, the door behind her closes, while the two other doors in that chamber (South and East) open, and she
has a choice of where to travel next. The exit is in the south-eastern-most chamber (the lower right corner; in
this case, coordinates 5, 5). Notice there could be dead ends in the Catacombs: the chambers where every door
closes at the same time. Prof. Adams really doesn't want to get caught in one of those.
The fastest solution to the maze above is ESWSEE. Here's a bigger example (19 by 11, in this case):
input data:
###################
# . . | . | | . | #
#.#.#|#.#|#.#.#|#.#
# . . . | . | . | #
#|#|#|#|#.#|#.#|#.#
# . | . . | | | | #
#.#.#|#.#|#.#.#.#|#
# | | . | | . | | #
#|#.#.#|#.#.#|#.#.#
# | | . | . . | | #
###################
answer:
SSSESEEENEEESE
The real labyrinth is, of course, much, much larger: it is 79 chars from West to East, and 39 chars from
North to South.
Naturally, the archeologist wants to find her way out of this dreadful place as quickly as possible. Can you help her? Your answer should be a sequence of uppercase letters, indicating the direction of her movement at each click.