Problem B. Blind Walk

Author:ACM ICPC NEERC 2008 Jury | Roman Elizarov   Time limit:2 sec
Input file:standard input   Memory limit:256 Mb
Output file:standard output  

Statement

ВНИМАНИЕ: на момент добавления задачи CATS не поддерживала интерактивные задачи. Поэтому проверка решений по этой задаче не производится.

This is an interactive problem.

Your task is to write a program that controls a robot which blindly walks through a maze. The maze is n × m (1 ≤ n, m ≤ 30) rectangular grid that consists of square cells. Each cell is either empty or blocked. All cells on the border of the maze are blocked. The robot starts in an empty cell. It can move south, west, north, or east to an adjacent empty cell. The robot is blind and has only bump sensors, so when it attempts to move it can either succeed or bump into blocked cell and fail.

The robot has to visit all empty cells in the maze. All cells are guaranteed to be reachable.

The picture shows sample maze where blocked cells are, filled and initial robot's location is designated with a circle.

The program must write to the standard output one line with robot's action and wait for a line in the standard input with a response, then write next action and read next response, and so on until all empty cells in the maze had been visited. The program must exit only when all cells have been visited. Empty cells may be visited multiple times. It is acceptable to move even after all cells had been visited.

Input file format

Each line of the standard input represents response on robot's action. It is either a string \t{EMPTY} if robot has successfully moved in the specified direction to an adjacent cell or a string \t{BLOCKED} if robot's movement has failed because the corresponding adjacent cell was blocked.

Output file format

Each line of the standard output represents robot's action. It is one of the following five strings: \t{SOUTH}, \t{WEST}, \t{NORTH}, \t{EAST}, or \t{DONE}. \t{DONE} must be printed when the robot has visited all empty cells. After printing \t{DONE} your program must exit. You must flush standard output after printing each action.

Sample tests

No. Input file (standard input) Output file (standard output)
1
NORTH
EAST
SOUTH
EAST
SOUTH
WEST
SOUTH
WEST
NORTH
WEST
WEST
NORTH
EAST
NORTH
DONE
BLOCKED
BLOCKED
EMPTY
BLOCKED
BLOCKED
EMPTY
BLOCKED
BLOCKED
EMPTY
EMPTY
BLOCKED
BLOCKED
EMPTY
BLOCKED

0.072s 0.015s 13