DWITE Online Computer Programming Contest

Velociraptor Maze

October 2007
Problem 5

A common problem is being chased through a maze by a hungry velociraptor. There is no time to think as to how one came to be in such a situation. A program is required to calculate the survival time of a human character.

The maze consists of hallways and has no open areas. There are no loops in the maze – that is, there is always only one possible path between any two points. There is just one exit, one human, and one velociraptor present in the maze. The only possible chance of survival is to make it to the exit before the velociraptor does. The velociraptor will also run towards the exit, covering twice as much ground “per turn” as the human figure.

Note: The velociraptor has no intelligence, but it knows its way to the exit. It will attack only when it occupies the same “square” as a human. In a case when the velociraptor is between a human and the exit, both will continue running until they meet at the exit location.

The input file DATA5.txt will contain two lines with one integer value each, R, C; 0 < R, C ≤ 10, representing the number of rows and columns that make up the maze. This is followed by R lines showing the maze layout, where:

The output file OUT5.txt will contain a single line for the result.

In an event that the velociraptor catches up with the human on the way to the exit, output a single integer representing the number of steps the human took before the event. The human has an advantage, so this will always be at least one, even if the velociraptor is right behind (or ahead).

In an event that the velociraptor makes it to the exit first, it will wait there. It will “catch up” right after the human figure steps onto the exit square.

In an event that the human and the velociraptor make it to the exit at the same time, the human still gets caught. Output the number of steps.

If in a given turn the human finds himself at the exit square, but the velociraptor does not, then output “escape” (lower case, no quotes).

Sample Input:
3
5
#####
V..HE
#####
Sample Output:
escape
Sample Input:
3
5
#####
H..EV
#####
Sample Output:
3