Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Dungeon Dawdler

Limits 3s, 512 MB · Interactive

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.

    Discussion

    Statistics


    100% Solution Ratio

    Tintin12Earliest, 1M ago

    Tintin12Fastest, 0.9s

    Tintin12Lightest, 33 MB

    Tintin12Shortest, 11950B

    Submit

    Login to submit