DWITE Online Computer Programming Contest
October 2007

Problem 5

Velociraptor Maze

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.

Input

The first line of input contains an integer R (0 < R ≤ 10), the number of rows in the maze. The second line contains an integer C (0 < C ≤ 10), the number of columns in the maze. R lines follow, each describing one row of the maze. '#' represents a wall, '.' an open space, 'E' the exit, 'H' the human, and 'V' the velociraptor.

Output

A single line containing the result. If the human reaches the exit before the velociraptor, output "escape". Otherwise, output the number of steps the human took before being caught by the velociraptor. Note that this will always be at least one. If the velociraptor reaches the exit before the human, it will wait there until the human arrives. If they reach the exit at the same time, the human is still caught.

Sample Input 1

3
5
#####
V..HE
#####

Sample Output 1

escape

Sample Input 2

3
5
#####
H..EV
#####

Sample Output 2

3

All Submissions
Best Solutions


Point Value: 10 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Mar 20, 2010

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

xiaowuc1 on Jun 29, 2014 - 5:29:11 pm UTC Ambiguity in Movement
  • (4/0)
The problem statement does not specifically tell you how to simulate the movement of the human and the velociraptor. It turns out that a rather nonintuitive simulation is required to get AC.

In particular, if you simulate time not in integer number of steps, you will get WA, and if you simulate time as, human moves one step closer immediately and velociraptor moves two steps closer immediately, you will also get WA.

The correct interpretation is that you simulate the human going one step first, then the velociraptor going one step, then the velociraptor going another step.