September 30th - October 5th, 1997 Drama - Greece
Day 1. Problem 1. The Running Man
 | |
 |
 |
 |
 |
 | |
| Day 1 | |
| Problem 1 | |
| Problem 2 | |
| Problem 3 | |
| Day 2 | |
| Problem 1 | |
| Problem 2 | |
| Problem 3 | |
| |
|
 |
|
 |
|
 |
|
 |
|
 |
| |
A man has escaped from prison, and trying to avoid the polie he enters a
square maze. The maze is composed of walking paths, doors and walls. Each
door connects two or more paths. The maze has only one entrance, which is
also the exit from the maze, and it is at the border of the maze.
The police, using a remote control device, can lock any door inside the maze,
except the entrance. Initially, all doors are unlocked. The location of the
running man into the maze is known, and it must be on the path. The movement
into the maze can have any direction, up, down, left, right but no diagonal steps
are allowed. Evidently, the running man can not be on a closed door or on a wall.
You are requested to help the police to trap the running man forever into the maze. However, ONLY ONE DOOR must be locked, and this door must be different than the entrance. The maximum size of the maze is 50 x 50.
INPUT
Your program should read the input from the file INPUT.TXT, which is an ASCII
file. The first line contains one positive integer number, denoting the side
of the maze in cells. The next line contains the location of the running man.
Each location is declared by a pair of numbers separated by a space character.
In each location the first number is the horizontal coordinate and the second
is the vertical coordinate. The numbering stars from the lower-left corner
of the maze (1,1). The following lines (until the end of the input file)
contain the description of the maze. The symbols are the following: D denotes
a door, E is the entrance/exit of the maze, P is a path and W denots a wall,
that no one can walk through. Any two symbols are separeted by a space character.
OUTPUT
Your program should produce its output into the file OUTPUT.TXT as follows:
The first line contains the string "YES" if it is possible to trap the running
man by locking only one door, or "NO" otherwise. If the answer is YES, the next
line contains an integer denoting how many doors qualify. The
rest of the file contains the locations of the doors (one location per line) that
if any of them is locked, then the running man can not escape the maze.
| INPUT.TXT | | OUTPUT.TXT |
5 4 4 W W W W W W W D P W W D P W W W P D P W W E W W W |
YES 1 3 4 |