Oh no! The wicked wizard Nocoproco has captured you and locked you
into his dungeon, from which there is no escape. Looks like you will
be here for a while, so you might as well make good use of the time
and scout out the place. Fortunately, there are no monsters lurking
about in the dungeon, so exploring should be relatively safe. But
there are still some complications.
There may be up to two hidden trapdoors in the dungeon.
Walking into a trapdoor causes you to
fall through it and end up in a different part of the dungeon.
To make matters worse, there are
few distinguishing features in the dungeon so
you have no immediate way of recognizing previously visited locations,
and it is easy to get disoriented. However, you do have a keen sense of direction and can always tell which way is north.
The dungeon is a rectangular grid where each cell is either a
wall, a plain open space, or a trapdoor. From an open space, the only
thing you can discern in the dim light is which of the four adjacent cells (in the
directions north, east, south, and west) are walls, and you can then walk
to any adjacent cell which is not a wall. If you walk into a
trapdoor, you fall into it before you can react, but you have time to observe
the four cells adjacent to the trapdoor before falling.
It is possible to go from every location in the dungeon to any other location
(but it may require using a trapdoor, as in Sample Interaction 1
below). The dungeon also consists of a single area -- if the trapdoors were
changed into plain open spaces it would still be possible to go from every location to any
other location. The endpoints of the trapdoors may be at any open
space in the dungeon, but not on another trapdoor, and the endpoints
of the two trapdoors are not at the same position. Your starting
point is neither a trapdoor nor an endpoint of a trapdoor.
Write a program to explore the dungeon and create a complete map of it.
Input
This is an interactive problem, proceeding in rounds. In each
round of interaction, your program first reads information about your
current surroundings, and then responds by taking an action.
The information about your current surroundings is given on a single
line.
The line starts with four characters $c_N$, $c_E$, $c_S$ and $c_W$ describing the surroundings of the cell
you just walked to (or for the first round, the starting cell), in the directions north, east, south and west respectively.
Each character is either $\texttt{\#}$, indicating that the cell in that
direction is a wall, or $\texttt{.}$, indicating that you can walk
there. Then on the same line follows either the word $\texttt{trap}$ if the
cell you walked to is a trapdoor, or $\texttt{ok}$ if it is not.
If the cell is a trapdoor, the line contains a third string,
describing the surroundings of the endpoint of the
trapdoor in the same format as above.
Output
There are two types of actions: moving to an
adjacent cell, and reporting that you are done.
To move to an adjacent cell, output a
single line containing one of $\texttt{N}$, $\texttt{E}$,$\texttt{S}$, and $\texttt{W}$, corresponding to moving north, east,
south, and west respectively. To report that you are done,
output a line containing$\texttt{done}$, followed by a complete map of the dungeon.
Output the map as a rectangular grid of minimum size, including all
walls seen. First output a line with two integers $h$ and $w$
indicating the height and width of the grid. Then output $h$ lines (from north to south)
each containing exactly $w$ characters (from west to east), using the following symbols:
$\texttt{\#}$for walls, and for other unreachable cells that are outside the dungeon.$\texttt{S}$for your starting position.$\texttt{A}$and$\texttt{B}$for the locations of the two trapdoors.$\texttt{a}$and$\texttt{b}$for the corresponding locations of the endpoints of the two trapdoors.$\texttt{.}$for the remaining walkable cells.
It does not matter which of the trapdoors you label$\texttt{A}$ and which of them you label$\texttt{B}$, as long as $\texttt{a}$ is the endpoint of the trapdoor
labelled $\texttt{A}$, and similarly for $\texttt{b}$. If there is only one trapdoor, you may label it either $\texttt{A}$ or $\texttt{B}$. After outputting the map the interaction ends and your program should exit.
There are at most $500$ reachable positions in
the dungeon. Your solution may take at most $10^5$ steps.
If you attempt to walk into a wall, your
program will be judged as Wrong Answer.
Remember to flush your standard output buffer after each action!
Here is a sample interaction:
< #.#. ok
> E
< #.#. trap .###
> N
< ##.. trap #.##
> E
< #.#. ok
> E
< #.#. ok
> E
< #.#. trap .###
> done
> 4 7
> #######
> #b.SAB#
> #####a#
> #######
This NCPC 2019 problem is licensed under the CC BY-SA 3.0 license.
You can find the original problem on the NCPC website.
