1167 - 7 Robotic Invasion
Time Limit : 4 Second
Memory Limit : 128 MB
Submission: 147
Solved: 12
- Description
- The pacifistic people of planet Pax are at war with the evil guys from planet Googol. Although they are
strictly pacifistic they have means of defense. Their cryptographers are able to routinely decrypt the com-
mands sent to Googol’s robots and they can – using huge amounts of energy – construct bogus commands.
It is the job of the Tactical Unit Defense (TUD) to find the best way to interfere with the command trans-
mission from Googol.
You are given a string of movements (each being a step to the north, east, south or west) and a map contain-
ing an invading robot from Googol and, possibly, several obstacles and traps.
Your task is to find a way to overcome the threat by changing as few movements as possible and guiding
the robot into a trap. A single change replaces a step by another direction or no movement at all.
A robot will move in the given direction if the position is not blocked or outside the given map. If given
such a direction, the robot does not move instead. - Input
- The first line contains the number of scenarios. For each scenario a line containing two integers 1 ≤ w, h ≤
100 separated by a single space is given, followed by h lines each containing w characters. This is a map of
the area.
Exactly one character is a R which is the starting position of the invading robot. Other characters are ‘ .’
to denote free positions, X to denote blocked positions and + to denote traps.
This is followed by a line containing an integer 0 ≤ c ≤ 100 and another line containing c characters of
communication. Each character is either N, E, S or W to denote a command to move one position up, right,
down or left, respectively. - Output
- The output for every scenario begins with a line containing “Scenario #i:”, where i is the number of
the scenario starting at 1.
Then print on a single line the string of movements (denoted by characters N, E, S, W and, for no
movement, X) that leads into a trap, of those the one that changes as few characters as possible, of those the
one that leads into a trap as early as possible, of those the lexicographically first. This string must have c
characters.
If no such string exists, output “impossible” on a single line. Terminate the output for the scenario
with a blank line.
- sample input
-
3 3 2 R+. ... 3 EEE 3 3 R.. .X+ ... 3 SSE 3 3 R.. ..+ ... 3 SSE
- sample output
-
Scenario #1: EEE Scenario #2: EES Scenario #3: ESE
- hint
- source
- TU-Darmstadt Programming Contest Team Contest 2008